94. Binary Tree Inorder Traversal

Description

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

For example:
Given binary tree [1,null,2,3],

tree

return [1,3,2].

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

Solution

DFS, time O(n), space O(1)

/**
 * 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) {
        List<Integer> inorder = new LinkedList<>();
        inorderTraversalRecur(root, inorder);
        return inorder;
    }
    
    public void inorderTraversalRecur(TreeNode root, List<Integer> inorder) {
        if (root == null) {
            return;
        }
        
        inorderTraversalRecur(root.left, inorder);
        inorder.add(root.val);
        inorderTraversalRecur(root.right, inorder);
    }
}

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

I use pushAllLeft() to push all the left children of one Node into the stack, so that my idea looks clear:

1. We push all the left children of root into the stack until there’s no more nodes.
2. Then we pop from the stack which we’d call cur.
3. Add cur to result list
4. Recursively call pushAllLeft() on cur's right child.

/**
 * 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) {
        List<Integer> inorder = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        pushAllLeft(root, stack);
        
        while (!stack.empty()) {
            TreeNode leftMost = stack.pop();
            inorder.add(leftMost.val);
            pushAllLeft(leftMost.right, stack);
        }
        
        return inorder;
    }
    
    public void pushAllLeft(TreeNode root, Stack<TreeNode> stack) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }
}

Common solution, time O(n), space O(h)

/**
 * 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) {
        List<Integer> list = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        
        while (!stack.empty() || p != null) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                list.add(p.val);    // add after left child visited
                p = p.right;
            }
        }
        
        return list;
    }
}