List a Tree's Values Left, Node, Right

Easy15–20 min

Topics

Binary TreeDFSStackTree Traversal

Companies

AmazonMicrosoftGoogleAdobe

You are given the root of a binary tree, where each node holds an integer val and has a left and a right child (either may be missing). Return the values of all nodes in the order you meet them when, at every node, you first walk the entire left subtree, then take the node itself, then walk the entire right subtree.

Writing this as a recursive helper is the direct approach. The same order can also be produced without recursion by keeping your own stack of the nodes that are still waiting for their turn.

Test Case 1:

Input:root = [4, 2, 7, 1, 3, null, 9]

Output:[1, 2, 3, 4, 7, 9]

Explanation:The tree lists its nodes level by level, null marking a missing child. Node 4 has children 2 and 7; node 2 has 1 and 3; node 7 has no left child and 9 as its right child. Reading left subtree, node, right subtree at every node gives the values in ascending order here.

Test Case 2:

Input:root = [5, null, 8, 6]

Output:[5, 6, 8]

Explanation:Node 5 has no left child, so it is visited first; then its right subtree, whose left child 6 comes before 8.

Test Case 3:

Input:root = []

Output:[]

Explanation:An empty tree has nothing to visit.

Constraints

◆0 ≤ number of nodes ≤ 100
◆−100 ≤ node.val ≤ 100
◆The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child
◆Visit every node's left subtree first, then the node itself, then its right subtree, and return the values in the order visited

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Walk

Good

Let the call stack do the bookkeeping. A helper visits a node by first walking its entire left subtree, then recording the node's own value, then walking its right subtree. A missing child (null) simply returns. Every node is entered once, so the time is O(n); the recursion is as deep as the tree is tall, so the extra space is O(h) (up to O(n) for a tree that is a single long chain).

TimeO(n)

SpaceO(h)

Java

Try it out

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

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

Optimal — Iterative Walk With an Explicit Stack

Optimal

Replace the call stack with a stack of your own. From the current node, keep going left, pushing every node passed on the way down. When there is nothing further left, pop the top node — that is the next value in order — record it, and move to its right child, then repeat the same walk down the left edge of that subtree. Stop when there is no current node and the stack is empty. Every node is pushed and popped exactly once (O(n) time), and the stack never holds more than one root-to-node path (O(h) space) — with no risk of overflowing the call stack on a very deep tree.