Binary Tree Inorder Traversal

easy tree dfs stack

Problem

Given the root of a binary tree, return the inorder traversal of its node values (left subtree, then root, then right subtree).

Inputroot = [1, null, 2, 3]

Output[1, 3, 2]

Inorder visits 1 (root), then descends right to 2, but first emits its left child 3 → [1, 3, 2].

level-order (use "null" for missing children)

def inorder_traversal(root):
    out, stack, node = [], [], root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out

function inorderTraversal(root) {
  const out = [], stack = [];
  let node = root;
  while (node || stack.length) {
    while (node) { stack.push(node); node = node.left; }
    node = stack.pop();
    out.push(node.val);
    node = node.right;
  }
  return out;
}

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

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> out;
    stack<TreeNode*> st;
    TreeNode* node = root;
    while (node || !st.empty()) {
        while (node) { st.push(node); node = node->left; }
        node = st.top(); st.pop();
        out.push_back(node->val);
        node = node->right;
    }
    return out;
}

Explanation

In-order means visit the left subtree, then the node, then the right subtree. Recursion does this naturally, but here we do it with an explicit stack so there is no hidden call stack.

The pattern has two parts. First, from the current node we keep going left, pushing every node we pass. This stacks up all the ancestors we still owe a visit to, with the smallest reachable node on top.

Then we pop one node, emit its value (this is the "visit the node" step), and switch to its right child. We repeat the whole process from there.

The loop runs while there is still a node to descend into or the stack isn't empty, so it naturally winds back up through ancestors after finishing each left branch.

Example on [1,null,2,3]: push 1, pop and emit 1, go right to 2, push 2 then its left child 3, pop and emit 3, pop and emit 2 → [1,3,2].

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