94. Binary Tree Inorder Traversal.md

8/17/2021

Python Tips:

• Python treats mutable (list, dictionary, pandas dataframe and series) and immutable (int, tuple, float) data types differently as they get processed inside a function. Immutable data type gets changed even if it's used inside a function.
• Python can use list to represent stack. list1 = [] stack1 = []
  • empty: !stack1
  • push: stack1.append(1)
  • pop: stack1.pop()
  • top: stack1[-1]

Algorithm 1:

Recursion Solution

1. initialize an vector/array
2. create an helper function to add int to array and return void
3. in helper funciton, go left-> add root-> go right
4. in helper, return when root is nullptr or None

• Time complexity: O(n). The time complexity is O(n) because the recursive function is T(n)=2⋅T(n/2)+1.
• Space complexity: The worst case space required is O(n), and in the average case it's O(logn) where nn is number of nodes.

C++

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        helper(root, ans);
        return ans;
    }
    
private:
    void helper(TreeNode* root, vector<int>& ans){
        if(!root){
            return;
        }
        helper(root->left, ans);
        ans.push_back(root->val);
        helper(root->right, ans);
    }
};

python

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        self.helper(root, ans)
        return ans
    def helper(self, root, ans):
        if not root:
            return
        self.helper(root.left, ans)
        ans.append(root.val)
        self.helper(root.right, ans)

Python one line:

def inorder(r):
    return inorder(r.left) + [r.val] + inorder(r.right) ir r else []

Algorithm 2:

Iterative Solution Using Stack

while(current || stack not empty):

1. push all nodes on left to the stack using while loop
2. pop the top node and set it to curret node
3. add current node to ans
4. set current node to current.right

• Time complexity: O(n).
• Space complexity: O(n).

C++

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> treeStack;
        TreeNode* cur = root;
        //adding !cur here to keep going when treeStack is empty at the begining
        while (cur || !treeStack.empty()){
            // pop all left nodes 
            while(cur){
                treeStack.push(cur);
                cur = cur->left;
            }
            cur = treeStack.top();
            treeStack.pop();
            ans.push_back(cur->val);
            cur = cur->right;
        }
        return ans;
    }
};

Python

# interative 
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        treeStack = []
        cur = root
        while cur or treeStack:
            while(cur):
                treeStack.append(cur)
                print(cur.val)
                cur = cur.left
    
            cur = treeStack.pop()
            
            ans.append(cur.val)
            cur = cur.right
        
        return ans

Algorithm 3

Another Way of Using Stack

1. add root to stack while stack pop top element if node exist append right, middle, left to stack. If right or left is None, append it as well if None pop again and add it to ans

Python

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            if node:
                stack.append(node.right)
                stack.append(node)
                stack.append(node.left)
            else:
                if stack:
                    node = stack.pop()
                    res.append(node.val)
        return res

Algorithm 4

Iterative Solution Using Morris Traversal

Step 1: Initialize current as root

Step 2: While current is not NULL,

If current does not have left child

a. Add current’s value

b. Go to the right, i.e., current = current.right

Else

a. In current's left subtree, make current the right child of the rightmost node

b. Go to this left child, i.e., current = current.left

• Time complexity: O(n).
• Space complexity: O(n).

C++ Code

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        TreeNode* cur = root;
        TreeNode* cur2;
        TreeNode* temp;
        while(cur){
            if(!cur->left){
                ans.push_back(cur->val);
                cur = cur->right;
            }
            else{
                cur2 = cur->left;
                // go to very right and connect with cur
                while(cur2->right){
                    cur2 = cur2->right;
                }
                cur2->right = cur;
                // go to left and set left to null.
                // otherwise it will comeback again.
                temp = cur;
                cur = cur->left;
                temp->left = nullptr;
            }
        }
        return ans;
    }
};

Python Code

# iterative using Morris Traversal
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        cur = root
        while cur:
            if not cur.left:
                ans.append(cur.val)
                cur = cur.right
            else:
                cur2 = cur.left
                # go to the right most of the cur2 and connect with cur
                while cur2.right:
                    cur2 = cur2.right
                cur2.right = cur
                temp = cur
                cur = cur.left
                # remove left node otherwise it will come back again. 
                temp.left = None
        
        return ans