The TreeNode class is the foundation for all binary tree problems. Must be instant.
class TreeNode:
def __init__(self, val, l=None, r=None):
self.val = val
self.left = l
self.right = rLeaf detection is used in path-sum, leaf-collection, and boundary traversal problems.
node.left is None and node.right is NoneRecursive node counting teaches divide-and-conquer tree thinking.
def count(node):
if not node: return 0
return 1 + count(node.left) + count(node.right)Height calculation is the basis for balanced-tree checks and diameter computation.
def height(node):
if not node: return 0
return 1 + max(height(node.left), height(node.right))Inorder on a BST yields sorted order. Foundation for validation and kth-smallest.
def inorder(node):
if not node: return
inorder(node.left)
visit(node)
inorder(node.right)Preorder visits root first. Used for serialization and tree construction.
def preorder(node):
if not node: return
visit(node)
preorder(node.left)
preorder(node.right)The trie node with children dict and end flag is the foundation for prefix-search data structures.
class TrieNode:
def __init__(self):
self.children = {}
self.end = FalseTrie insert walks and creates nodes character by character. O(word length) per insert.
def insert(root, word):
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.end = TrueTrie search checks end flag at the final node. Distinguishes full words from prefixes.
def search(root, word):
node = root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.endPrefix search returns True if any word starts with the prefix. No end-flag check needed.
def starts_with(root, prefix):
node = root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return TrueRecursive trie deletion prunes empty branches. Checks if children remain before removing.
def delete(node, word, i=0):
if i == len(word):
node.end = False
return len(node.children) == 0
c = word[i]
if delete(node.children[c], word, i+1):
del node.children[c]
return not node.end and len(node.children) == 0Diameter is the max left_height + right_height at any node. Track global max during DFS.
dia = 0
def h(n):
global dia
if not n: return 0
l, r = h(n.left), h(n.right)
dia = max(dia, l + r)
return 1 + max(l, r)Level-order collects node values per level. Foundation for zigzag and right-side-view.
from collections import deque
q = deque([root])
res = []
while q:
lvl = []
for _ in range(len(q)):
n = q.popleft()
lvl.append(n.val)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
res.append(lvl)Carry max-so-far down the path. A node is good if its value >= the path max.
def dfs(n, mx):
if not n: return 0
good = 1 if n.val >= mx else 0
mx = max(mx, n.val)
return good + dfs(n.left, mx) + dfs(n.right, mx)The traversal order determines WHEN you process the root relative to children. Pick based on information flow direction.
TREE TRAVERSAL — WHEN TO USE WHICH
───────────────────────────────────
PREORDER (root → left → right):
→ Process root BEFORE children
→ Serialization, copying tree, prefix expression
→ "top-down" information passing
INORDER (left → root → right):
→ BST: gives sorted order!
→ Kth smallest, validate BST, convert BST to list
POSTORDER (left → right → root):
→ Process root AFTER children
→ "bottom-up" computation (height, size, subtree sums)
→ Delete tree, evaluate expression tree
LEVEL ORDER (BFS):
→ Level-by-level processing
→ Right side view, zigzag, level averages
→ Shortest path in unweighted tree
QUICK DECISION:
Need sorted from BST? → inorder
Need to compute from leaves → postorder
Need top-down propagation? → preorder
Need level-by-level? → BFSBST's ordering invariant enables O(log n) search. But it must hold for entire subtrees, not just direct children.
BST vs BINARY TREE — KEY DIFFERENCES
─────────────────────────────────────
BINARY TREE: BST:
No ordering constraint left < root < right (all nodes)
Search: O(n) Search: O(h), avg O(log n)
Insert: append anywhere Insert: find correct position
Inorder: no special order Inorder: SORTED output
BST INVARIANT (must hold for ENTIRE subtree):
Every node in left subtree < root
Every node in right subtree > root
(Not just immediate children!)
BST OPERATIONS & COMPLEXITY:
Search: O(h) → go left if target < node, else right
Insert: O(h) → search for position, add leaf
Delete: O(h) → 3 cases: leaf, 1 child, 2 children
Min/Max: O(h) → leftmost / rightmost node
Inorder: O(n) → sorted traversal
BALANCED BST: h = O(log n) → all ops O(log n)
SKEWED BST: h = O(n) → degenerates to linked listRecursive is cleaner, iterative is safer for deep trees. Know both — interviews often ask for iterative after recursive.
RECURSIVE vs ITERATIVE TRAVERSAL
────────────────────────────────
RECURSIVE: ITERATIVE:
+ Clean, readable + No stack overflow risk
+ Natural for trees + Can pause/resume
- Python recursion limit + O(1) extra space (Morris)
- Stack frame overhead - More complex code
WHEN TO USE ITERATIVE:
□ Deep trees (>1000 nodes) → recursion limit
□ Need to process nodes in specific order with state
□ Morris traversal needed (O(1) space)
□ Interview asks for iterative explicitly
CONVERSION PATTERN:
Recursive → Iterative:
1. Create explicit stack
2. Push root
3. While stack not empty:
- Pop node
- Process it (preorder) or push for later (inorder)
- Push children (right first, then left for preorder)
MORRIS TRAVERSAL: O(1) space
Uses threaded tree (temporary right pointers)
Only for inorder/preorderTop-down pushes state down. Bottom-up bubbles results up. Many tree problems become trivial once you pick the right direction.
TOP-DOWN vs BOTTOM-UP DFS
─────────────────────────
TOP-DOWN: pass info FROM root TO leaves
def dfs(node, info_from_parent):
# use info_from_parent
dfs(node.left, updated_info)
dfs(node.right, updated_info)
Examples:
Path sum: pass remaining sum down
Max depth: pass current depth down
Same tree: pass corresponding nodes
BOTTOM-UP: gather info FROM leaves TO root
def dfs(node):
left_info = dfs(node.left)
right_info = dfs(node.right)
return combine(left_info, right_info, node)
Examples:
Height: return 1 + max(left_h, right_h)
Diameter: return max depth, update global diameter
Balanced: return height, check balance
DECISION:
"Does parent need to tell children something?" → top-down
"Does parent need results from children?" → bottom-up
Some problems need BOTH (e.g., max path sum)Recursive: left → right → root. Iterative trick: do root → right → left (modified preorder) then reverse.
def postorder(root):
res = []
def dfs(node):
if not node: return
dfs(node.left)
dfs(node.right)
res.append(node.val)
dfs(root)
return res
# Iterative (reverse of modified preorder):
def postorder_iter(root):
if not root: return []
stack, res = [root], []
while stack:
node = stack.pop()
res.append(node.val)
if node.left: stack.append(node.left)
if node.right: stack.append(node.right)
return res[::-1]Push all left children, pop and process, go right. The fundamental iterative tree pattern.
def inorder(root):
res, stack = [], []
cur = root
while cur or stack:
while cur: # go left as far as possible
stack.append(cur)
cur = cur.left
cur = stack.pop() # process node
res.append(cur.val)
cur = cur.right # go right
return resBST search: go left if target < node, right if target > node. O(h) time. Must be instant.
def searchBST(root, val):
while root:
if val == root.val: return root
elif val < root.val: root = root.left
else: root = root.right
return None
# Recursive:
def searchBST_rec(root, val):
if not root or root.val == val: return root
if val < root.val: return searchBST_rec(root.left, val)
return searchBST_rec(root.right, val)Search for the insertion point, create new node there. Always inserts as a leaf. O(h) time.
def insertIntoBST(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insertIntoBST(root.left, val)
else:
root.right = insertIntoBST(root.right, val)
return root
# Iterative:
def insertIntoBST_iter(root, val):
node = TreeNode(val)
if not root: return node
cur = root
while True:
if val < cur.val:
if not cur.left: cur.left = node; break
cur = cur.left
else:
if not cur.right: cur.right = node; break
cur = cur.right
return rootPass valid range [lo, hi) down. Left child must be < root, right must be > root. Check entire subtree, not just children.
def isValidBST(root):
def dfs(node, lo, hi):
if not node: return True
if node.val <= lo or 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'))Swap left and right children recursively. The classic 'Homebrew' interview question. Must be instant.
def invertTree(root):
if not root: return None
root.left, root.right = invertTree(root.right), invertTree(root.left)
return rootBoth null → True. One null → False. Values equal AND both subtrees same → True. Base case for subtree check.
def isSameTree(p, q):
if not p and not q: return True
if not p or not q: return False
return (p.val == q.val and
isSameTree(p.left, q.left) and
isSameTree(p.right, q.right))Mirror check: compare left.left with right.right AND left.right with right.left. Like 'same tree' but crossed.
def isSymmetric(root):
def mirror(a, b):
if not a and not b: return True
if not a or not b: return False
return (a.val == b.val and
mirror(a.left, b.right) and
mirror(a.right, b.left))
return mirror(root.left, root.right)At each node in root, check if it's the same tree as subRoot. O(m*n) brute force.
def isSubtree(root, subRoot):
if not root: return False
if isSameTree(root, subRoot): return True
return (isSubtree(root.left, subRoot) or
isSubtree(root.right, subRoot))
def isSameTree(p, q):
if not p and not q: return True
if not p or not q: return False
return (p.val == q.val and
isSameTree(p.left, q.left) and
isSameTree(p.right, q.right))Subtract node value as you go down. At a leaf, check if remaining equals node value. Top-down DFS.
def hasPathSum(root, targetSum):
if not root: return False
if not root.left and not root.right:
return root.val == targetSum
return (hasPathSum(root.left, targetSum - root.val) or
hasPathSum(root.right, targetSum - root.val))Backtracking on tree: append node, recurse, pop. Collect path copy at valid leaves. Classic tree + backtrack combo.
def pathSum(root, targetSum):
res = []
def dfs(node, remaining, path):
if not node: return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
res.append(path[:]) # copy!
dfs(node.left, remaining - node.val, path)
dfs(node.right, remaining - node.val, path)
path.pop() # backtrack
dfs(root, targetSum, [])
return resBottom-up DFS. At each node: update global max with left+node+right. Return single branch for parent to use.
def maxPathSum(root):
res = [float('-inf')]
def dfs(node):
if not node: return 0
left = max(dfs(node.left), 0) # ignore negative paths
right = max(dfs(node.right), 0)
# path through this node as turning point
res[0] = max(res[0], left + node.val + right)
# return max single-side path for parent
return node.val + max(left, right)
dfs(root)
return res[0]BST property: if both targets < root go left, both > root go right, otherwise root is LCA. O(h) time.
def lowestCommonAncestor(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return rootIf both sides return non-null, current node is LCA. Otherwise, LCA is on the non-null side. O(n) time.
def lowestCommonAncestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right: return root # split point = LCA
return left or rightPreorder with null markers (#). Each node becomes: val, left_subtree, right_subtree. Null markers preserve structure.
def serialize(root):
res = []
def dfs(node):
if not node:
res.append('#')
return
res.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ','.join(res)Consume preorder tokens with an iterator. '#' = null leaf. Recursion naturally reconstructs the tree structure.
def deserialize(data):
vals = iter(data.split(','))
def dfs():
val = next(vals)
if val == '#': return None
node = TreeNode(int(val))
node.left = dfs()
node.right = dfs()
return node
return dfs()Iterative inorder (sorted order for BST). Count down k, return when k reaches 0. O(H + k) time.
def kthSmallest(root, k):
stack = []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
k -= 1
if k == 0: return cur.val
cur = cur.rightBFS level-by-level. Take the last node of each level. Standard level-order with level_size tracking.
from collections import deque
def rightSideView(root):
if not root: return []
res = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
res.append(node.val) # rightmost in level
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return resMorris-like: for each node with left child, find its inorder predecessor, link right subtree there, move left to right.
def flatten(root):
cur = root
while cur:
if cur.left:
# find rightmost of left subtree
prev = cur.left
while prev.right:
prev = prev.right
# rewire
prev.right = cur.right
cur.right = cur.left
cur.left = None
cur = cur.rightPreorder[0] is root. Find root in inorder → left subtree is inorder[:mid], right is inorder[mid+1:].
def buildTree(preorder, inorder):
if not preorder: return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = buildTree(preorder[1:mid+1], inorder[:mid])
root.right = buildTree(preorder[mid+1:], inorder[mid+1:])
return root
# Optimized: use hashmap for O(1) index lookup
def buildTree_opt(preorder, inorder):
idx = {v: i for i, v in enumerate(inorder)}
it = iter(preorder)
def build(lo, hi):
if lo > hi: return None
val = next(it)
node = TreeNode(val)
mid = idx[val]
node.left = build(lo, mid - 1)
node.right = build(mid + 1, hi)
return node
return build(0, len(inorder) - 1)O(1) space traversal using temporary threaded links. Each edge traversed at most twice → O(n) time.
def morrisInorder(root):
res = []
cur = root
while cur:
if not cur.left:
res.append(cur.val)
cur = cur.right
else:
# find inorder predecessor
pred = cur.left
while pred.right and pred.right != cur:
pred = pred.right
if not pred.right:
pred.right = cur # create thread
cur = cur.left
else:
pred.right = None # remove thread
res.append(cur.val)
cur = cur.right
return resThe for-range-len(q) trick processes one level at a time. Without it you get plain BFS without level grouping.
from collections import deque
q = deque([root])
result = []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
result.append(level)