DSA · Chapter 20 of 40
Tree Traversals
Traversal means visiting every node in a defined order. Depth-first traversals are preorder (node, left, right), inorder (left, node, right) and postorder (left, right, node). Breadth-first traversal visits level by level using a queue.
Inorder traversal of a binary search tree returns the values in sorted order, which is a very common interview fact.
Choosing a traversal
Preorder copies or serialises a tree, inorder sorts a BST, postorder deletes or computes results from children first, level order finds shortest depth.
Complexity
Every traversal is O(n) time. Recursive DFS uses O(h) stack space; BFS uses O(w) queue space for the widest level.
Example 1 (python)
def inorder(node, out):
if not node:
return
inorder(node.left, out)
out.append(node.val)
inorder(node.right, out)
return out
print(inorder(root, []))Output
[2, 1, 3]Left subtree, then node, then right subtree.
Example 2 (python)
from collections import deque
def level_order(root):
out, q = [], deque([root])
while q:
node = q.popleft()
out.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return out
print(level_order(root))Output
[1, 2, 3]A queue produces level-by-level order.
Key points
- Preorder, inorder and postorder are depth-first.
- Level order is breadth-first and uses a queue.
- Inorder on a BST yields sorted values.
- All traversals are O(n) time.
💡 Note: Memorise the three DFS orders by where the node itself is visited.