Inorder traversal of a Tree

Given the root node of a Tree , return the node values in a list in inorder.

For example,

For the below tree:

The inorder traversal is [ 0,2,3,4,5,6,7,8,9]

Try out the solution here:

https://leetcode.com/problems/binary-tree-inorder-traversal

Solution:

There are three ways to do inorder traversal:

• Using Recursion
• Using Stack
• Morris Traversal (without using any additional memory of recursion or stack)

Let’s look into each of them.

Approach 1 – Recursion:

In recursion , you traverse the left node of the tree recursively , add the current node value to the output list and traverse the right node of the tree recursively.\

here is the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    List<Integer> output = new ArrayList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        
    
        inorder(root);
        
        return output;
        
    }
    
    
    public void inorder(TreeNode node){
        
             if(node != null){
                inorder(node.left);  
                output.add(node.val);
                inorder(node.right);
            }
    }
}

Time complexity:

O(n) since we traverse through all the nodes once.

Space complexity:

O(n) for the worst case ( a single chain tree) where you allocate memory for each recursive call

Approach 2 – Using Stack

In this approach you just replace the recursion call with stack.

First you keep moving to the left of the tree until you reach the left most node and push all the nodes into the stack along the way.

Then you pop the top node , add its value to the output.

Then you move to the right node and continue the same process.

You stop doing the above until the current node pointer is empty OR the stack is empty.

Here is the code :

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    
    public List<Integer> inorderTraversal(TreeNode root) {
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> output = new ArrayList<>();
        
        TreeNode current = root;
        
        while(current!= null || !stack.isEmpty()){
            
            
            while(current != null){
                
                stack.add(current);
                
                current = current.left;
            }
            
            current = stack.pop();
            
            
            output.add(current.val);
            
            
            current = current.right;
        }
        
        return output;
    }
}

Time complexity :

Same as previous approach since we traverse through all the nodes O(n)

Space complexity:

Since we push all the nodes into the stack , it is O(n)

Approach 3 – Morris Traversal

Both the previous approaches use additional space .

There is a way to do inorder traversal without using additional space.

But this method modifies the original tree.

The resultant tree is called Threaded Binary Tree.

Here is the general idea:

Cut the left sub tree of current root node.

Find the right most node of the left sub tree.

Append the current root node to this right most node.

Now repeat the above steps for the left sub tree which was just cut. ( cut its left subtree and append the current parent node to the rightmost node of the left subtree)

Once there is no more left subtree to cut move to the right node of current node and do the above again.

Let us look at this using an illustration.

Let’s take our input tree:

The root node is 6.

The root node of the left sub tree is 2.

And the right most node of the left sub tree is 5.

So lets cut this let subtree and make the right most node point to the root node 6.

Here is the updated tree in the first iteration:

As you see we have cut the left sub tree and placed it on top of the root node.

Now let’s do the same for the left sub tree just cut.

It has a left subtree with a single node 0.

We will cut this and place on top of the node 2:

Now current node is 0.

It has no left sub tree.

So we move right to node 2.

It also has no left tree , so we move right to 4.

It has a left subtree.

So we cut that tree and place it on top of 4 and make its root node 3 as current node.

Now the current node is 3 and it has no left tree.

So we move to the right node 4.

The node 4 also has no left tree so we move to 5.

The node 5 also has no left tree so we move to 6.

The node 6 also has no left tree so we move to 8.

The node 8 has a left subtree .

We will place this left subtree (with a single node 7) on top of the current node.

Now 7 is the current node.

It doesnt have a left tree so we move to 8 which also has no left tree so we move to 9.

Node 9 has no left tree either so we move to its right which is null.

And now we exit.

Now if you look at the tree and get the node values from the top they represent the inorder :

[0,2,3,4,5,6,7,8,9].

Here is the algorithm:

1. Initialize current node to root
2. While current node is not null do the following:
   • Check if left sub tree is null
     • If so add current node value to output
     • Move to the right subtree
   • If left subtree is not null then do the following
     • Go to the root of the left sub tree
     • Keep moving to the right of the left subtree until the right most bottom most node is reached
     • Make this node point to the current node
     • Go to the left subtree root node of the current node and continue step 2

Here is the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    
    public List<Integer> inorderTraversal(TreeNode root) {
     
    List<Integer> output = new ArrayList<Integer>();
        
        TreeNode current = root;
        TreeNode prev = null;
        
        
        while(current != null){
            
            
            if(current.left == null){
                
                output.add(current.val);
                
                current = current.right;
            }else{
                
                
                prev = current.left;
                
                
                while(prev.right != null){
                    
                    prev = prev.right;
                    
                    
                }
                
                
                prev.right = current;
                //we store the current node in a temp variable because we //need to make its left sub tree as null after making the left subtree as //current node
                TreeNode temp = current;
                //moving to current left subtree and making it current
                current = current.left;
                //making left of previous current node as null
                temp.left = null;
                
            }
            
            
        }
        
        
        return output;
                       
        }
         
}

Time complexity:

Time complexity is O(n) since every node is visited twice or thrice in the worst case – while finding the predecessor and while locating the current node and while adding the current node to the output.

What is the time complexity of just finding the predecessor?

While finding the predecessor of a node you navigate through its left node (let’s say L )and then through the right subtree of this left node (prev = prev.right in the code).

And then you find the predecessor of this left node L during which you won’t cross the previous predecessor route.

So same node won’t be processed twice while finding the predecessor.

So total time complexity of finding the predecessor for the entire tree is in the worst case O(n).

Space complexity:

There is no extra space required other than the output so space complexity is O(1)