Foundation drill for this topic
Easy Recursive Max
In 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).
Try to write it from scratch before scrolling down.
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)Quick recall drills to reinforce this pattern.
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 rootHeight 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))