Leetcode 94. Binary Tree Inorder Traversal

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Solution 1: Recursion

Recursion is the go-to method when dealing with tree data structures. In this problem, the tree needs to be printed out as inorder, which means to put root node in between left subtree and right subtree. Therefore, the recursion solution is done by recursively calling a funtion with a tree node as the argument. In the function, itself is called on left child node of the input tree node, which will properly print out the left subtree by inorder, followed by printing out the input tree node, and eventually calling itself again on the right child to print out right subtree inorder.

The code is as follows:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // Solution 1: Recursion
        if (root == null) return new ArrayList<Integer>();
        List<Integer> ans = new ArrayList<>();
        traverse(ans, root);
        return ans;
    }

    private void traverse(List<Integer> res, TreeNode root) {
        if (root.left != null) traverse(res, root.left);
        res.add(root.val);
        if (root.right != null) traverse(res, root.right);
    }
}

Solution 2: Iteration

Another solution to the this problem is by iteration instead of recursion, which is much more tricky. Unlike recursion, which natually preserves the pointer to each root of subtrees when the recursion goes deep (by returning to the level of that root), iteration need stacks to do the trick. Specifically, a stack can be used to store a node when its left subtree is not null because we need to work on the left subtree first. After the left subtree is done, the stack can pop out the node at top which should be the immediate parent to the finished subtree. Then the right subtree can be worked on before another pop-up from stack, and goes on until the right-most node is reached.

The code is as follows:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // Solution 2: Iteration
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;

        TreeNode cur = root;
        Stack<TreeNode> s = new Stack<>();
        while (cur != null || !s.isEmpty()) {
            while (cur != null) {
                s.push(cur);
                cur = cur.left;
            }
            cur = s.pop();
            ans.add(cur.val);
            cur = cur.right;
        }
        return ans;
    }
}