Binary Tree Inorder Traversal

Problem

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

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

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

Solution

Recursive Solution Time: T(n) = 2 * T(n / 2) + 1 = O(n)

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        traversal(root, res);
        return res;
    }

    private void traversal(TreeNode node, List<Integer> res) {
        if (node == null) return;
        traversal(node.left, res);
        res.add(node.val);
        traversal(node.right, res);
    }
}

Iterative Solution using Stack: O(n) time, O(n) space

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !s.isEmpty()) {
            //push left subtrees 
            while (cur != null) {
                s.push(cur);
                cur = cur.left;
            }
            cur = s.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

Analysis

Recursive solution is pretty easy
The iterative solution uses stack and push the left node first
When reach the end, it adds the val of current node and then move to right subtree