0094.md

94. Binary Tree Inorder Traversal

Level:

Topic:

Similar Problem:

• 144. Binary Tree Preorder Traversal
• 145. Binary Tree Postorder Traversal

Question

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

Input: root = [1,null,2,3]
Output: [1,3,2]

Intuition

Recursive:

• Left -> Node -> Right

Iterative:

DFS inorder Stack

• no need to store right node since it will be as root and push its left nodes to the stack

1. push until no more left node found
2. pop the top (deepest unadded left node), adds its value to the list
3. the current node should be righ child of its own
   • and because of assigning current node to its right, it will never traverse the visited node's left child again

Code

Time: O(n)
Space: O(n)

Iterative

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();

    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }

        root = stack.pop();
        ans.add(root.val);
        root = root.right;
    }
    return ans;
}

Recursive

List<Integer> ans = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
    inorder(root);
    return ans;
}

private void inorder(TreeNode root) {
    if (root == null)
        return;
    inorder(root.left);
    ans.add(root.val);
    inorder(root.right);
}