Given a Binary Tree, find its Boundary Traversal. The traversal should be in the following order:

Left boundary nodes: defined as the path from the root to the left-most node ie- the leaf node you could reach when you always travel preferring the left subtree over the right subtree. Leaf nodes: All the leaf nodes except for the ones that are part of left or right boundary. Reverse right boundary nodes: defined as the path from the right-most node to the root. The right-most node is the leaf node you could reach when you always travel preferring the right subtree over the left subtree. Exclude the root from this as it was already included in the traversal of left boundary nodes. Note: If the root doesn't have a left subtree or right subtree, then the root itself is the left or right boundary.

so to solve this problem we have to divide the problem into 3 parts as follows:

1. LeftBoundary: if a root exists we need to go to the left and push back the value into the answer array else we do the same with the right.

void leftBoundary(Node* root,vector<int>& ans)
    {
        if(root){
            if(root->left){
                ans.push_back(root->data);
                leftBoundary(root->left,ans);  
            } 
            else if(root->right){
                ans.push_back(root->data);
                leftBoundary(root->right,ans);
            } 
        }
        return;
    }

1. LeafNodes: we just have to get all the leaf nodes.

   void leafNodes(Node* root,vector<int>& ans)
    {
        if(!root) return;
        if(isLeaf(root))
        {
            ans.push_back(root->data);
            return;
        }
        leafNodes(root->left,ans);
        leafNodes(root->right,ans);
    }
   

2. RightBoundary: Same as the left boundary but in this case, we need to reverse the order so we can use a stack or a vector to store the result and reverse it along the way.

void rightBoundary(Node* root,vector<int>& ans)
    {
        if(root){
            if(root->right){
                temp.push_back(root->data);
                rightBoundary(root->right,ans);  
            } 
            else if(root->left){
                temp.push_back(root->data);
                rightBoundary(root->left,ans);
            } 
        }
        return;
    }
    void revRightBound(vector<int>& temp,vector<int> &ans)
    {
        for(int i=temp.size()-1;i>=0;i--)
        {
            ans.push_back(temp[i]);
        }
    }

So by breaking the problem into 3 we get easy steps to solve this but there are some conditions we need to be careful of that is left boundary only contains the left view of the tree except the last leaf node. and the right boundary is the right view of the tree except for root and leaf node.

/* A binary tree Node
struct Node
{
    int data;
    Node* left, * right;
}; */

class Solution {
    vector<int> temp;
public:
    bool isLeaf(Node* root)
    {
        return (root->left==NULL && root->right==NULL)?true:false;
    }
    void leftBoundary(Node* root,vector<int>& ans)
    {
        if(root){
            if(root->left){
                ans.push_back(root->data);
                leftBoundary(root->left,ans);  
            } 
            else if(root->right){
                ans.push_back(root->data);
                leftBoundary(root->right,ans);
            } 
        }
        return;
    }
    void rightBoundary(Node* root,vector<int>& ans)
    {
        if(root){
            if(root->right){
                temp.push_back(root->data);
                rightBoundary(root->right,ans);  
            } 
            else if(root->left){
                temp.push_back(root->data);
                rightBoundary(root->left,ans);
            } 
        }
        return;
    }
    void revRightBound(vector<int>& temp,vector<int> &ans)
    {
        for(int i=temp.size()-1;i>=0;i--)
        {
            ans.push_back(temp[i]);
        }
    }
    void leafNodes(Node* root,vector<int>& ans)
    {
        if(!root) return;
        if(isLeaf(root))
        {
            ans.push_back(root->data);
            return;
        }
        leafNodes(root->left,ans);
        leafNodes(root->right,ans);
    }
    vector <int> boundary(Node *root)
    {
        //Your code here
        vector<int> ans;
        if(!root) return {};

        ans.push_back(root->data);

        leftBoundary(root->left,ans);
        if(!isLeaf(root))
        leafNodes(root,ans);
        rightBoundary(root->right,ans);
        revRightBound(temp,ans);

        return ans;
    }
};