Binary Tree Inorder Traversal

NeetCode: Binary Tree Inorder Traversal · LeetCode: 94. Binary Tree Inorder Traversal · Difficulty: Easy

Given the root of a binary tree, return the inorder traversal of its node values: visit the left subtree, then the node itself, then the right subtree.

Example

Text

Input:  [1, null, 2, 3]     (1 has right child 2, and 2 has left child 3)
Output: [1, 3, 2]

Input:  []
Output: []

Trees are given in LeetCode's level-order array form: the first value is the root, and each following pair of values holds the left and right child of the next node that exists, in the order the nodes were placed. null marks a missing child, and a missing node has no children listed. The tree(Integer...) helper in each program builds a TreeNode from such an array. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed. For a binary search tree, inorder visits the values in sorted order, which is why this traversal shows up so often.

Brute force: recursion

The definition translates directly into code: traverse the left subtree, record the node, traverse the right subtree. The call stack tracks the current position. The recursive helper appends to one shared ArrayList.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private void walk(TreeNode node, List<Integer> out) {
        if (node != null) {
            walk(node.left, out);
            out.add(node.val);
            walk(node.right, out);
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        walk(root, out);
        return out;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.inorderTraversal(tree(1, null, 2, 3)));
        System.out.println(s.inorderTraversal(tree(4, 2, 6, 1, 3, 5, 7)));
        System.out.println(s.inorderTraversal(tree()));
    }
}

Output

[1, 3, 2]
[1, 2, 3, 4, 5, 6, 7]
[]

The recursion is already linear. Its weakness is that the depth equals the tree height, and a very long chain of nodes can exhaust the thread stack and throw StackOverflowError. Time: O(n). Space: O(h) for the recursion, where h is the height (O(n) for a chain).

Optimal: iterative with an explicit stack

The call stack in the recursive version holds the nodes whose left subtree is still being explored. An explicit stack on the heap does the same job. Walk left as far as possible, pushing each node. When there is no further left child, pop a node, record it, and move to its right child. Then repeat the "go left" step from there.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            out.add(cur.val);
            cur = cur.right;
        }
        return out;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.inorderTraversal(tree(1, null, 2, 3)));
        System.out.println(s.inorderTraversal(tree(4, 2, 6, 1, 3, 5, 7)));
        System.out.println(s.inorderTraversal(tree()));
    }
}

Output

[1, 3, 2]
[1, 2, 3, 4, 5, 6, 7]
[]

The stack is an ArrayDeque on the heap, used through push and pop, so a very deep tree cannot cause a StackOverflowError. Time: O(n); every node is pushed and popped once. Space: O(h) for the stack.

Morris traversal. An inorder traversal can run in O(1) extra space by temporarily rewiring the tree. For each node with a left subtree, find the rightmost node of that left subtree (its inorder predecessor) and point its empty right link back to the current node; this thread lets the walk climb back up without a stack. On arriving at the node a second time via the thread, remove the thread, record the node, and go right. Every edge is walked a constant number of times, so it stays O(n). It mutates the tree while running, so it is not safe alongside other readers. It changes right links temporarily and restores each one before it finishes.