Easy · Iterative Tree Stack
Understand → Visualise → Practice.
A binary tree uses heap-style level indices with null holes. Return its inorder values.
Inorder visits the whole left subtree, then the node, then the right subtree. An explicit stack does this without recursion: go left as far as possible, then visit and turn right.
Push nodes while moving to the left child.
Pop a node and record its value.
Move to its right child and repeat until the stack is empty and there's no current node.
O(n) time and O(h) space.
Recording the value before exploring the left subtree gives preorder, not inorder.
Read the full guides first: Binary Trees and Traversals, Binary Search Trees, Graphs, BFS and DFS, Weighted Graphs, Dijkstra and Union–Find.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.