Leetcode: Binary Tree Inorder Traversal

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].

Note: Recursive solution is trivial, could you do it iteratively?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

Understand the problem:
The problem asks for inorder traversal of a binary tree. So first of all, we need to understand what is the inorder traversal? Basically, inorder traversal is visit left child first, then its parent, then right child. 

Recursive Solution:
The recursive solution is very straight-forward, considering the recursive nature of the tree. We just need to recursively go to the left children first until to the leaves recursively. Print each node and go the right children recursively. 

Code (Java):

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

Iterative Solution:
Since the question asks for iterative solution, we can explore a solution without using recursive approach. Again, for a tree-based problem using iterative approach, we could employ using a stack to store the intermediate nodes.  The basic idea is to iterate the left children and add to the stack. Use a pointer to trace the current position. If no left children, pop an element and update the pointer to the right children. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (root == null) return result;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        
        TreeNode p = root;
        while (!stack.empty() || p != null) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode temp = stack.pop();
                result.add(temp.val);
                p = temp.right;
            }
        }
        return result;
    }
}

Discussion:
The time complexity is O(n). The space complexity is O(h), where h is the height of the tree. It is O(h) instead of O(n) because the stack at most stores the height of the tree elements. 

Summary:
In this post we studied the inorder binary tree traversal. The recursive solution is neat but requires deep understanding of the details. The iterative solution is tricky. Unlike the preorder iterative solution we pop an item first, the inorder traversal used a pointer to track the current position of the tree. Be careful of that idea in tree-based problems.