Inorder / PreOrder/PostOrder : T(C) = O(N), SC = O(N) — Recursive Solution

Inorder Morris Traversal:

Morris Inorder Traversal is a tree traversal algorithm aiming to achieve a space complexity of O(1) without recursion or an external data structure.

1. Uses concept of threaded Binary tree by attaching current node with its inorder successor.

2. There are 3 cases:

   1. There is no left child of current node— print current value and set current = current→right.
   2. There is a left subtree, and the right-most child of this left subtree is pointing to null→ set right child of rightmost tree of left subtree to current and move current = current→left.
   3. There is a left subtree, and the right-most child of this left subtree is pointing to some node → print current and set right child of rightmost tree of left subtree to NULL and move current= current→right

       vector<int> inorderTraversal(TreeNode* root) {
           vector<int> result;
           if(!root)
               return result;
           TreeNode * curr = root;
           while(curr){
           // case 1
               if(!curr->left){
                   result.push_back(curr->val);
                   curr= curr->right;
               }
               //case 2 and 3
               else if(curr->left) {
                   TreeNode* temp = curr->left;
                   while(temp->right && temp->right!=curr){
                       temp = temp->right;
   
                   }
                   //case 2
                   if(!temp->right) {
                       temp->right = curr;
                       curr= curr->left; 
                   }
                   //case 3
                   else if(temp->right==curr){
                       temp->right=NULL;
                       result.push_back(curr->val);
                       curr= curr->right;
                   }
               }
   
           }
                   return result;
       }
   

   TC : 0(N), S(C) = O(1);

PreOrder Morris Traversal

Slide variation in cases

1. Uses concept of threaded Binary tree by attaching current node with its inorder successor.
2. There are 3 cases:
   1. There is no left child of current node— print current value and set current = current→right. // same as inorder morris
   2. There is a left subtree, and the right-most child of this left subtree is pointing to null→ set right child of rightmost tree of left subtree to current then print current value and then move current = current→left.
   3. There is a left subtree, and the right-most child of this left subtree is pointing to some node → set right child of rightmost tree of left subtree to NULL and move current= current→right

vector<int> getPreOrderTraversal(TreeNode *root)
{
    vector<int> result;
        if(!root)
            return result;
        TreeNode * curr = root;
        while(curr){
            if(!curr->left){
                result.push_back(curr->data);
                curr= curr->right;
            }
            //case 2 and 3
            else if(curr->left) {
                
                TreeNode* temp = curr->left;
                while(temp->right && temp->right!=curr){
                    temp = temp->right;

                }
                //case 2
                if(!temp->right) {
                    result.push_back(curr->data);
                    temp->right = curr;
                    curr= curr->left; 
                }
                //case 3
                else if(temp->right==curr){
                    temp->right=NULL;
                    
                    curr= curr->right;
                }
            }

        }
                return result;
}

Left View of Binary tree

Use queue and print first element at every level using level order traversal

vector<int> leftView(Node *root)
{
    queue<Node*>q;
    vector<int>res;
    if(!root)
        return res;
    q.push(root);
    while(!q.empty()){
        int s = q.size();
        for(int i=0;i<s;i++){
            Node * node = q.front();
            q.pop();
            if(i==0){
                res.push_back(node->data);
            }
            if(node->left){
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }
        }
    }
    return res;
}

Bottom View Of Binary Tree