Leetcode 94 Binary Tree Inorder Traversal

Leetcode 94 Binary Tree Inorder Traversal

The problem description is as follow:

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,3,2].

In case you are not familiar with inorder tree traversal, the following graph would help:

The in-order traversal for previous tree is A, B, C, D, E, F, G, H, I.

Recursive Approach

Edit Binary Tree Inorder Traversal on GitHub

Recursive approach is pretty straight forward. The order of inorder is :

1. Left Child 
2. Parent Node
3. Right Child

Thus the code will be:

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

The time complexity of recursive approach is O(n) since we are just traversing the whole tree once. The space complexity of recursive approach is O(log n).

Iterative Approach

Edit Binary Tree Inorder Traversal on GitHub

When it comes to iterative approach in tree traversal, always use a stack or queue. We could use a stack to imitate the recursive process we did above:

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
 
        if(root == null)
            return res; 
 
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //define a pointer to track nodes
        TreeNode p = root;
        while(!stack.empty() || p != null){
            if(p != null){
                stack.push(p);
                p = p.left;
            }else{
                TreeNode t = stack.pop();
                res.add(t.val);
                p = t.right;
            }
        }
 
        return res;
    }
}

The time complexity of recursive approach is O(n) since we are just traversing the whole tree once. The space complexity of recursive approach is O(log n).

Morris Traversal Algorithm

Edit Binary Tree Inorder Traversal on GitHub

Actually there’s a better way to solve the problem. Instead of using O(log n) space, we could solve it with O(l) space.

In order to solve the problem with O(l) space, the most important question is how to traverse back to parent node from child node. Morris traversal introduce threaded binary tree. In threaded binary tree, we don’t have to assign additional space to every node pointing to the predecessor and successor, nor do we have to save the nodes into stack.

1. If left child of current node is empty, output current node. Set current's right child as current node
2. If left child of current node is not empty, find the in-order traversal predecessor node in its left subtree 
- If predecessor's right child is empty, predecessor's right child = current node. Current node = current node's left child.
- If predecessor's right child is current node, set predecessor's right child back to empty (recover structure of tree). Output current node. Set current node = current node's right child.
- There won't be other possibility according to definition of predecessor.

Repeat process 1 and 2 until current node is empty.

The following graph would help a lot:

Here comes the code:

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur != null) {
            if(cur.left == null) {
                res.add(cur.val);
                cur = cur.right;
            }
            else {
                pre = cur.left;
                while(pre.right!=null && pre.right!=cur)
                    pre = pre.right;
                if(pre.right==null) {
                    pre.right = cur;
                    cur = cur.left;
                }
                else {
                    pre.right = null;
                    res.add(cur.val);
                    cur = cur.right;
                }
            }
        }
        return res;
    }
}

Since we are traversing each node at most twice, the time complexity is still O(n) and we are only using O(1) extra space.