6 drills · 6 pattern exercises · 12 micro drills
Patterns used in this topic, with difficulty breakdown.
Find the longest path between any two nodes in a binary tree, measured in edges.
All 6 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Find the deepest node in a binary tree that is an ancestor of both given nodes.
Recurse left and right. If p and q are in different subtrees, the current node is the LCA. If both are on one side, the LCA is in that subtree.
Prompt
Given a binary tree and two nodes p and q, find their lowest common ancestor (LCA).
Solution
def lowest_common_ancestor(root, p, q):
if root is None or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root # p and q are in different subtrees
return left if left else right
# Test: tree = [3,5,1,6,2,0,8], LCA(5,1) = 3, LCA(5,4) = 5In plain English: Check if any path from the root to a leaf adds up to a given target number.
Subtract the current node's value from the target as you descend. At a leaf, check if the remaining target is zero.
Prompt
Given a binary tree and a target sum, determine if there is a root-to-leaf path that sums to the target.
Solution
def has_path_sum(root, target):
if not root:
return False
target -= root.val
if not root.left and not root.right:
return target == 0 # leaf: check if sum matches
return has_path_sum(root.left, target) or has_path_sum(root.right, target)
# Test: tree [5,4,8,11,null,13,4,7,2,null,null,null,1], target=22 => True
# Path: 5->4->11->2In plain English: Find the longest path between any two nodes in a binary tree, measured in edges.
At each node, the longest path through it is left_height + right_height. Track the global maximum while computing heights bottom-up.
Prompt
Find the diameter of a binary tree — the length of the longest path between any two nodes (in edges).
Solution
def diameter_of_binary_tree(root):
diameter = [0]
def height(node):
if not node:
return 0
lh = height(node.left)
rh = height(node.right)
diameter[0] = max(diameter[0], lh + rh) # path through this node
return 1 + max(lh, rh)
height(root)
return diameter[0]
# Test: tree [1,2,3,4,5] => diameter = 3 (path 4->2->1->3)In plain English: Check whether the left and right halves of a binary tree are mirror images of each other.
Two subtrees are mirrors if their roots match and each tree's left subtree mirrors the other's right subtree — recurse with crossed pairs.
Prompt
Check if a binary tree is symmetric (a mirror image of itself).
Solution
def is_symmetric(root):
def is_mirror(t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2:
return False
return (t1.val == t2.val and
is_mirror(t1.left, t2.right) and # cross-compare
is_mirror(t1.right, t2.left))
return is_mirror(root, root) if root else True
# Test: tree [1,2,2,3,4,4,3] => True
# Test: tree [1,2,2,null,3,null,3] => FalseIn plain English: Convert a binary tree to a string so it can be saved, then rebuild the tree from that string.
Preorder traversal with null markers uniquely identifies a tree. Serialize: visit, left, right. Deserialize: read values and recurse, using an iterator.
Prompt
Serialize a binary tree to a string and deserialize it back to the original tree structure.
Solution
class Codec:
def serialize(self, root):
vals = []
def preorder(node):
if not node:
vals.append('#') # null marker so structure is unambiguous
return
vals.append(str(node.val))
preorder(node.left)
preorder(node.right)
preorder(root)
return ','.join(vals)
def deserialize(self, data):
# iterator lets recursive calls consume tokens in order without index bookkeeping
vals = iter(data.split(','))
def build():
v = next(vals)
if v == '#':
return None
node = TreeNode(int(v))
node.left = build()
node.right = build()
return node
return build()
# Test: tree [1,2,3] => "1,2,#,#,3,#,#" => back to treeIn plain English: Look at a binary tree from the right side and list the nodes you can see at each level.
Level-order traversal where you record the last node at each level — that is the rightmost node visible from the right side.
Prompt
Given a binary tree, return the values of the nodes you can see from the right side, ordered from top to bottom.
Solution
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
result.append(node.val) # last node in level = rightmost
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
# Test: tree [1,2,3,null,5,null,4] => [1, 3, 4]6 exercises: spot the signals, pick the method, avoid the trap.
Find the LCA of two nodes in a binary tree.
Signals
Recurse left and right. If both return non-null, current node is LCA. If one is null, return the other. O(n).
Trap
For BSTs, you can use the BST property to go left/right more efficiently. But for general trees, full recursion is needed.
Find the diameter (longest path between any two nodes).
Signals
Height recursion, update global max = left_h + right_h at each node. O(n).
Trap
The diameter doesn't necessarily pass through the root! Must check at every node.
Serialize a binary tree to a string and reconstruct it.
Signals
Serialize: preorder with '#' for nulls. Deserialize: read values in order, recurse. O(n).
Level-order serialization with null markers also works. Same O(n).
Trap
Need null markers to distinguish tree shapes. Without them, different trees can have same traversal.
Is there a root-to-leaf path that sums to a target?
Signals
Recurse with target - node.val. At leaf: return target == node.val. O(n).
Trap
Must check at leaf nodes, not at null nodes. A leaf has no children.
Return values visible from the right side (rightmost node per level).
Signals
Level-order BFS. For each level, the last node is the rightmost. O(n).
DFS visiting right before left. First node at each new depth is the answer. O(n).
Trap
It's not just the rightmost branch — nodes from the left can appear if right subtree is shorter.
Check if a binary tree is its own mirror image.
Signals
is_mirror(left, right): both null → True. One null → False. Values match AND subtrees mirror. O(n).
BFS with pairs: enqueue (left.left, right.right) and (left.right, right.left). Same O(n).
Trap
Don't just check if inorder traversal is a palindrome — that's necessary but not sufficient.
12 quick recall drills to reinforce this topic.
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 rightSwap 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 rootDiameter 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)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))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()Preorder 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)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 resBFS 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 resMirror 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)Both 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))