Drag across the board. Click it, then use ← → to step and Space to play.
A tree is a board of gates. The root sits at the top. Every gate (a node) has at most two grooves leading down, to a left child and a right child, and a gate with no grooves below it is a leaf. There are two ways to walk the board. DFS rolls all the way down one path before backing up, and keeps that path on the call stack. BFS clears the board one row (level) at a time, with a queue. In a BST every gate sends smaller values left and larger values right, so a search rolls down a single path.
FIG. 6 · Eleven gates, built by inserting 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7 into a BST. Gates are laid out left to right in sorted order, so a plumb line dropped from each one lands in order. The red marks whatever the code is touching right now. Callouts: A root, B leaf, C depth and height.
def max_depth(node): # DFS: base case, recurse, combine
if not node:
return 0
return 1 + max(max_depth(node.left), max_depth(node.right))
def level_order(root): # BFS
q = deque([root] if root else [])
levels = []
while q:
level = []
for _ in range(len(q)): # one full level
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
levels.append(level)
return levels
def bst_search(root, target): # go left if smaller, right if larger
while root:
if target < root.val:
root = root.left
elif target > root.val:
root = root.right
else:
return True
return False
def inorder(node, out): # left, node, right: sorted order in a BST
if not node:
return
inorder(node.left, out)
out.append(node.val)
inorder(node.right, out)
def isValidBST(root): # LeetCode 98
def dfs(node, lo, hi): # every node must lie strictly inside (lo, hi)
if not node:
return True
if not (lo < node.val < hi):
return False
return dfs(node.left, lo, node.val) and dfs(node.right, node.val, hi)
return dfs(root, float('-inf'), float('inf'))
def rightSideView(root): # LeetCode 199
res, q = [], deque([root] if root else [])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i == size - 1: # last node of this level
res.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
Checking each node against its parent is not enough: every node must fit between bounds set by all its ancestors. DFS passes (lo, hi) down the tree. This tree hides a 6 inside the left subtree of 5. Trigger: "valid BST".
Standing on the right, you see one node per level: the last one. BFS processes the tree level by level, so keep the last node of each level. Trigger: "right side view", "level order".
n is the number of nodes, h the height (longest root-to-leaf path), w the width (most nodes on one level). The last column fills in when a run finishes.
| Operation | Time | Space | Why | Last run on the bench |
|---|---|---|---|---|
| DFS (recursive) | O(n) | O(h) | Every node is visited once. The call stack holds one frame per node on the current path. | not run yet |
| BFS (queue) | O(n) | O(w) | Every node is queued and removed once. The queue holds about one level at a time. | not run yet |
| BST search, insert, remove | O(log n) balanced · O(n) skewed | O(1) iterative | One comparison per level, so the cost is the height: log n if balanced, n if every node has only one child. | not run yet |
| Inorder traversal · TreeSet / TreeMap iteration | O(n) | O(h) | Left, node, right visits a BST in sorted order. TreeMap get, put and remove are O(log n) because the tree is kept balanced. | not run yet |
DFS keeps one root-to-leaf path: O(h). BFS keeps a whole level: O(w). In a balanced tree h ≈ log n but the bottom level holds about n/2 nodes, so DFS uses far less memory. In a long skewed chain it is the reverse: h = n while w = 1.
For every node, everything in its left subtree is smaller and everything in its right subtree is larger. That ordering is what makes search walk one path, and what makes inorder traversal come out sorted.
A heap only promises that a parent is smaller than its children, nothing about left vs right. So the minimum is always at the root (O(1) to read, O(log n) to remove), but searching for an arbitrary value is O(n).
Each node holds one value, kept sorted. Add, remove and contains are O(log n), and iterating gives the values in order. Python has no built-in TreeSet: use sortedcontainers.SortedList, or bisect on a sorted list.
Nodes are ordered by key and carry a value. get, put and remove are O(log n), plus "floor" and "ceiling" lookups that a hash map cannot do. In Python: sortedcontainers.SortedDict.
Base case at None, recurse into the children, combine the answers.
A queue, processing one full level per round.
Keep the data ordered while it keeps changing.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def max_depth(node): # DFS: base case, recurse, combine
if not node:
return 0
return 1 + max(max_depth(node.left), max_depth(node.right))
from collections import deque
def level_order(root): # BFS
q = deque([root] if root else [])
levels = []
while q:
level = []
for _ in range(len(q)): # one full level
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
levels.append(level)
return levels
def bst_search(root, target): # go left if smaller, right if larger
while root:
if target < root.val:
root = root.left
elif target > root.val:
root = root.right
else:
return True
return False