Start practising

Binary Tree Inorder Traversal (Recursive) (Trees & BST)

Easy Trees & BST Recursion Original on LeetCode

Binary Tree Inorder Traversal (Recursive) is a easy trees & bst problem solved with the recursion pattern. The best approach, morris traversal (o(1) space), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from recursive dfs up.

Problem

Return the inorder traversal (left, node, right) of a binary tree.

Examples

Example 1

Input
root = [4, 2, 6, 1, 3]
Output
[1, 2, 3, 4, 6]

Example 2

Input
root = []
Output
[]

Constraints

  • The tree has 0 to 100 nodes.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Recursive DFSO(n)O(h)
Morris traversal (O(1) space)O(n)O(1)

1Recursive DFS

TimeO(n)
SpaceO(h)Call stack as deep as the tree height h.

Visit the left subtree, record the node, then visit the right subtree. On a BST this lists the values in sorted order.

  1. if node == null return.
  2. inorder(left); add(node.val); inorder(right).
Java
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        inorder(root, out);
        return out;
    }

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

2Morris traversal (O(1) space)

TimeO(n)Each edge is walked at most a few times.
SpaceO(1)

Temporarily link each node's inorder predecessor back to the node, so you can return up the tree without a stack, then remove the link on the second visit.

  1. If cur has no left child: visit, go right.
  2. Else find pred = rightmost node of cur.left.
  3. If pred.right is null: pred.right = cur, go left. Else: pred.right = null, visit cur, go right.
Java
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left == null) {
                out.add(cur.val);
                cur = cur.right;
            } else {
                TreeNode pred = cur.left;
                while (pred.right != null && pred.right != cur) pred = pred.right;
                if (pred.right == null) { pred.right = cur; cur = cur.left; }
                else { pred.right = null; out.add(cur.val); cur = cur.right; }
            }
        }
        return out;
    }
}

Edge cases to test

  • Empty tree
  • Only left children (skewed)

Hints

Hint 1

Inorder = left, root, right. Write the recursion exactly in that order.

FAQ

What is the best time complexity for Binary Tree Inorder Traversal (Recursive)?

Morris traversal (O(1) space) runs in O(n) time and O(1) extra space. Each edge is walked at most a few times.

Which pattern does Binary Tree Inorder Traversal (Recursive) use?

It is a trees & bst problem that uses the recursion pattern. Other problems with the same pattern: Binary Tree Preorder Traversal (Recursive), Binary Tree Postorder Traversal (Recursive), Binary Tree Inorder Traversal (Iterative).

Is there a brute force solution for Binary Tree Inorder Traversal (Recursive)?

Yes. Recursive DFS takes O(n) time and O(h) space. Visit the left subtree, record the node, then visit the right subtree.

Which edge cases should I test for Binary Tree Inorder Traversal (Recursive)?

Empty tree; Only left children (skewed).