Boundary Traversal of Binary Tree

Problem Link:

1. https://www.codingninjas.com/studio/problems/boundary-traversal-of-binary-tree_790725?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf

2. https://leetcode.com/problems/boundary-of-binary-tree/description/

Hint video:

NOTE: At time 2.00 mins, 3 is also a leaf node so you won't add on level order traversal of left subtree.

void helper(TreeNode<int>* root, vector<int> &bound){

    if(root==NULL){
        return;
    }

    if(root->left==NULL && root->right==NULL){
        bound.push_back(root->data);
        return;
    }

    helper(root->left, bound);
    helper(root->right, bound);

    return;
}

vector<int> traverseBoundary(TreeNode<int> *root)
{
    // Write your code here.

    vector<int> bound;
    queue<TreeNode<int>*> q;
    q.push(root);

    // level order traversal on left excluding leaf
    while(!q.empty() && root->left!=NULL){
        TreeNode<int>* node = q.front();
        q.pop();

        // ignoring leaf
        if(node->left==NULL && node->right==NULL){
            break;
        }

        bound.push_back(node->data);

        if(node->left!=NULL){
            q.push(node->left);
        }

        if(node->left==NULL && node->right!=NULL){
            q.push(node->right);
        }
    } 

    if(bound.size()==0){
        bound.push_back(root->data);
    }

    TreeNode<int>* temp = root;

    // finding leaf nodes using recursive traversal
    helper(temp, bound);

    while(!q.empty()){
        q.pop();
    }

    if(root->right!=NULL){
        q.push(root->right);
    }

    // temp array to store right traversal
    vector<int> rb;

    // level order traversal on right 
    while(!q.empty()){
        TreeNode<int>* node = q.front();
        q.pop();

        if(node->left==NULL && node->right==NULL){
            break;
        }

        rb.push_back(node->data);

        if(node->right!=NULL){
            q.push(node->right);
        }

        if(node->right==NULL && node->left!=NULL){
            q.push(node->left);
        }
    }

    // reversing it before storing
    reverse(rb.begin(), rb.end());

    for(int i=0;i<rb.size();i++){
        bound.push_back(rb[i]);
    }

    return bound;

}