10 drills · 10 pattern exercises · 18 micro drills
Patterns used in this topic, with difficulty breakdown.
Add a new value to a binary search tree so that the BST property is preserved.
All 10 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Add a new value to a binary search tree so that the BST property is preserved.
BST property guides you left or right at each node — the first None you reach is where the new node belongs.
Prompt
Insert a value into a binary search tree.
Solution
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bst_insert(root, val):
if root is None: # None = empty slot, insert here
return TreeNode(val)
if val < root.val:
root.left = bst_insert(root.left, val)
else:
root.right = bst_insert(root.right, val)
return rootIn plain English: Look up whether a value exists in a binary search tree.
BST property halves the search space at each step — go left if smaller, right if larger, like binary search on a tree.
Prompt
Search for a value in a BST. Return the node or None.
Solution
def bst_search(root, val):
if root is None or root.val == val:
return root # base: found or exhausted
if val < root.val:
return bst_search(root.left, val) # BST: smaller goes left
return bst_search(root.right, val)
# Iterative:
def bst_search_iter(root, val):
while root and root.val != val:
root = root.left if val < root.val else root.right # halve search space
return rootIn plain English: Find how many levels deep a binary tree goes from root to its deepest leaf.
Height is defined recursively: a node's height is 1 + the taller subtree — base case None returns -1 so leaves get height 0.
Prompt
Find the height of a binary tree.
Solution
def height(node):
if node is None: # None has height -1, leaf has height 0
return -1
return 1 + max(height(node.left), height(node.right))
# Test: single node => 0, node with one child => 1In plain English: Visit every node in a binary tree in left-root-right order (gives sorted order for BSTs).
Inorder visits left before root before right — for BSTs this produces sorted output because left < root < right at every node.
Prompt
Return the inorder traversal of a binary tree as a list.
Solution
def inorder(node, result=None):
# left, visit, right = sorted for BST
if result is None:
result = []
if node:
inorder(node.left, result)
result.append(node.val)
inorder(node.right, result)
return result
# BST [4,2,6,1,3] inorder => [1,2,3,4,6]In plain English: Visit every node in a binary tree in root-left-right order.
Preorder visits the root first — useful for copying or serializing a tree since you see each node before its children.
Prompt
Return the preorder traversal of a binary tree as a list.
Solution
def preorder(node, result=None):
# visit first, then children
if result is None:
result = []
if node:
result.append(node.val)
preorder(node.left, result)
preorder(node.right, result)
return result
# BST [4,2,6,1,3] preorder => [4,2,1,3,6]In plain English: Visit every node in a binary tree level by level, from top to bottom.
A queue processes nodes in discovery order — processing one full level before the next gives breadth-first traversal.
Prompt
Return the level-order traversal of a binary tree as list of lists.
Solution
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level = []
# process entire level before next
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)
return result
# Test: BST [4,2,6,1,3] => [[4], [2,6], [1,3]]In plain English: Check whether a binary tree satisfies the BST rule (left < root < right) at every node.
Passing tightening (lo, hi) bounds down the tree catches violations that a simple left < root < right check at each node would miss.
Prompt
Check if a binary tree is a valid binary search tree.
Solution
def is_valid_bst(node, lo=float('-inf'), hi=float('inf')):
if node is None:
return True
if node.val <= lo or node.val >= hi:
return False
return (is_valid_bst(node.left, lo, node.val) and # bounds tighten as we descend
is_valid_bst(node.right, node.val, hi))
# Test: [2,1,3] => True; [5,1,4,null,null,3,6] => FalseIn plain English: Find the longest path between any two nodes in a binary tree, counted in edges.
The diameter through any node = left_height + right_height. Compute heights bottom-up (post-order) and track the maximum diameter seen. The answer might not pass through the root.
Prompt
Given the root of a binary tree, return the length of the diameter (the longest path between any two nodes, measured in edges).
Solution
def diameter_of_binary_tree(root):
diameter = 0
# post-order: compute subtree heights bottom-up so parent can combine them
def height(node):
nonlocal diameter
if not node:
return 0
left = height(node.left)
right = height(node.right)
# longest path through this node is left_height + right_height
diameter = max(diameter, left + right)
return 1 + max(left, right)
height(root)
return diameter
# Test: tree [1,2,3,4,5] (2 is left child of 1, 3 is right)
# diameter = 3 (path: 4->2->1->3 or 5->2->1->3)In plain English: Imagine looking at a binary tree from the right side. List what you'd see from top to bottom.
BFS level by level. The last node in each level is visible from the right. Alternatively, DFS visiting right before left, recording the first node at each new depth.
Prompt
Given the root of a binary tree, return the values of nodes visible from the right side, ordered from top to bottom.
Solution
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if i == level_size - 1: # rightmost in this level
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# Test: tree [1,2,3,null,5,null,4]
# right_side_view => [1,3,4]In plain English: Count nodes where no ancestor on the path from the root has a larger value.
DFS passing the maximum value seen so far on the path from root. A node is good if its value >= max_so_far. Update max_so_far as you recurse deeper.
Prompt
Given a binary tree root, a node X is 'good' if there are no nodes with a greater value on the path from root to X. Return the number of good nodes.
Solution
def good_nodes(root):
def dfs(node, max_so_far):
if not node:
return 0
# node is "good" when no ancestor on root-to-node path had a larger value
good = 1 if node.val >= max_so_far else 0
new_max = max(max_so_far, node.val) # propagate tighter bound to children
return good + dfs(node.left, new_max) + dfs(node.right, new_max)
return dfs(root, root.val)
# Test: tree [3,1,4,3,null,1,5]
# good nodes: 3 (root), 4, 3 (left-left), 5 => count = 410 exercises: spot the signals, pick the method, avoid the trap.
Insert a value into a binary search tree.
Signals
Compare value with node, go left or right. When you hit None, create the new node. O(h) time.
Trap
Don't forget to return the modified subtree root (or assign node.left/right = recursive call).
Search for a value in a BST. Return the node or None.
Signals
Compare with root, recurse left or right. O(h) time — O(log n) for balanced, O(n) for skewed.
Trap
Iterative version is also fine and avoids stack overhead: while node: go left or right.
Find the height of a binary tree.
Signals
Recurse on both children, return 1 + max(left, right). O(n) visiting all nodes.
Level-order traversal, count levels. Same O(n) but more complex code.
Trap
Clarify the height convention with the interviewer: edge-count vs node-count (off by one).
Return the inorder traversal of a binary tree as a list.
Signals
Recurse left, append current, recurse right. O(n) time.
Iterative with explicit stack: push lefts, pop and visit, go right. Same O(n).
Trap
Know all three traversals (in/pre/post) and when each is useful. Inorder = sorted for BSTs.
Return the preorder traversal of a binary tree as a list.
Signals
Append current, recurse left, recurse right. O(n) time.
Iterative: push root, pop and visit, push right then left (so left is processed first).
Trap
In iterative version, push right before left — stack is LIFO so left gets processed first.
Return the level-order traversal of a binary tree as list of lists.
Signals
Use a queue. Process one full level at a time using len(queue) at level start. O(n).
DFS passing depth parameter, append to result[depth]. Works but less intuitive for 'level-order'.
Trap
Standard BFS doesn't group by level. The key trick: for each level, process exactly len(queue) nodes.
Check if a binary tree is a valid binary search tree.
Signals
Recurse with (lo, hi) bounds. Left child tightens hi, right child tightens lo. O(n).
Inorder traversal should produce sorted order — check that each value > previous. O(n).
Trap
Checking only node.left.val < node.val < node.right.val is WRONG — misses non-local violations.
Find the diameter (longest path between any two nodes) of a binary tree.
Signals
Post-order: return height. At each node, update diameter = max(diameter, left_h + right_h). O(n).
Same approach. The diameter is a side effect of computing heights.
Trap
Diameter is NOT always through the root. It can be entirely in a subtree.
Given a binary tree, return the values visible from the right side (rightmost node at each level).
Signals
Level-order traversal. Append the last node of each level to result. O(n).
DFS going right first. Track level; if level == len(result), append value. O(n).
Trap
DFS right-first works but BFS is more intuitive. Don't assume it's just the rightmost branch.
Count nodes where the node's value is greater than or equal to all values on the path from root.
Signals
Pass max_so_far down. If node.val >= max_so_far, it's good. Update max and recurse. O(n).
Same DFS. Every node is visited once.
Trap
The initial max_so_far is root.val (root is always good). Don't forget to include the root.
18 quick recall drills to reinforce this topic.
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 rootBST 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 rootThe 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 = rBST 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)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))Diameter 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)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 rootInorder 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)Leaf detection is used in path-sum, leaf-collection, and boundary traversal problems.
node.left is None and node.right is NoneThe 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)Level-order BFS uses a queue with size tracking. Core pattern for tree breadth-first problems.
from collections import deque
q = deque([root])
while q:
for _ in range(len(q)):
node = q.popleft()
if node.left: q.append(node.left)
if node.right: q.append(node.right)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)Pass 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'))BFS 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 resPreorder 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)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)Recursive node counting teaches divide-and-conquer tree thinking.
def count(node):
if not node: return 0
return 1 + count(node.left) + count(node.right)