Pattern visualizer

Binary Tree Inorder Traversal

Inorder means a node is recorded only after its entire left subtree has been, and before any of its right subtree. A node seen for the first time therefore cannot be consumed yet — it waits on the call stack while the traversal drives left, and gets its turn as the frames unwind. Watch the stack: the number of paused frames is exactly the number of nodes still owed their turn. Animated on: Given the root of a binary tree, return the inorder traversal of its nodes' values — for the tree with root 2, left subtree 7 (children 1 and 6) and right subtree 5 (right child 9)..

Left subtree, then the node, then the right subtree — the call stack holds each node until its left side is done.

time O(n)space O(h) call stackstep 1 / 16

Call stack

inorder(2)

line 4

At 2. Its left child 7 must be fully handled before 2 may be recorded, so inorder(2) pauses on the stack and recurses left.

Pseudocode

1FUNCTION inorder(node):
2  IF node = null:
3    RETURN
4  inorder(node.left)
5  APPEND node.val TO out
6  inorder(node.right)
7RETURN out

← / → step · space play · Home restart

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap