---

title: 'Trees Problem Set-1' author: 'zaheen' topic : 'trees' subtopic: ['tree-problems'] description: 'In this blog we will cover some problems related to trees and their different traversals.'

Tree Problem Set-1

Summary for the blog ⌨️⌨️ : In this blog we will cover some problems related to trees and their different traversals.

• Trees
• DSA
• Tree-traversals

Sl No	problems/ Algorithms	Link
1	Zig zag traversal	Problem 1
2	Boundary traversal	Problem 2

Problem No - 1

Explanation :-

• Here we do a level order traversing in the tree ,There will be a variable assigned to determine whether to go from left to right or vice versa.
• we will process each level of tree (i.e. rows) and store the results of that particular row in a temporary vector.
• At the end of processing of each level we will copy the elements from the temporary vector to a result vector , and return it.

class Solution{
    public:
    
    vector<int> solve(Node* root){
        queue<Node*>q;
        q.push(root);
        bool leftToright =true;
        vector<int>res;
        
        while(!q.empty()){
            int size =q.size();
            vector<int>ans(size);
            
            for(int i=0;i<size;i++){
                Node* temp = q.front();
                q.pop();
                
                int index = leftToright?i:size-i-1;
                ans[index]=temp->data;
                
                if(temp->left){
                    q.push(temp->left);
                }
                if(temp->right){
                    q.push(temp->right);
                }
            }
            leftToright=!leftToright;
            for(auto i:ans){
                res.push_back(i);
            }
        }
        
        return res;
        
    }
    //Function to store the zig zag order traversal of tree in a list.
    vector <int> zigZagTraversal(Node* root)
    {
    	// Code here
    	return solve(root);
    	
    }
};

---

Problem No - 2

Explanation :-

• Since we are traversing the tree on only its boundaries , here the algorithm is divided into 3 parts. one for traversing left most part, the the leaf nodes then the right most part
• In left part we wont traverse the root node leaf nodes, because it is handled separately.
• In leaf node part. we will call it for both left and right part of the root node, since if there is only one node in the tree, we don't want to store the root node again in the answer.
• In right hand part we will do it recursively. but there is a catch in it, we should take the right side part in the reverse order of traversal. checkout the code below.

class Solution {
public:

    void leftsolve(Node*root,vector<int> &ans){
        if(root==NULL || (root->left==NULL &&root->right==NULL)){
            return;
        }
        
        ans.push_back(root->data);
        if(root->left){
        leftsolve(root->left,ans);
        }
        else{
            leftsolve(root->right,ans);
        }
    }
    
    
    void leafsolve(Node*root,vector<int>& ans){
        if(root==NULL){
            return;
        }
        
        if(root->left==NULL &&root->right==NULL){
            ans.push_back(root->data);
            return;
        }
        
            leafsolve(root->left,ans);
            leafsolve(root->right,ans);
    }
    
    void rightsolve(Node*root,vector<int>& ans){
        if(root==NULL || (root->left==NULL &&root->right==NULL)){
            return;
        }
        
        if(root->right){
            rightsolve(root->right,ans);
        }
        else{
            rightsolve(root->left,ans);
        }
        ans.push_back(root->data);
    }
    
    vector <int> boundary(Node *root)
    {
        //Your code here
        vector<int>ans;
        ans.push_back(root->data);
        leftsolve(root->left,ans);
        leafsolve(root->left,ans);
        leafsolve(root->right,ans);
        rightsolve(root->right,ans);
        return ans;
    }
};

---