Linked Lists and Trees
Pointer reversal without losing the list, the four traversals and when each is the right one, and the recursion depth that turns a correct solution into a crash.
Linked lists test pointer discipline; trees test recursion. Both have a small number of techniques that cover almost every question.
The setup
import sys
from collections import deque
class ListNode:
def __init__(self, val=0, nxt=None):
self.val, self.next = val, nxt
def build_list(values):
dummy = tail = ListNode()
for v in values:
tail.next = ListNode(v)
tail = tail.next
return dummy.next
def to_list(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
print(to_list(build_list([1, 2, 3, 4, 5])))[1, 2, 3, 4, 5]Note build_list already uses the dummy-head trick — no special case for the first node.
Reversal: the three-pointer dance
def reverse_list(head):
prev, curr = None, head
while curr:
nxt = curr.next # 1. SAVE — without this the rest is unreachable
curr.next = prev # 2. REVERSE
prev, curr = curr, nxt # 3. ADVANCE
return prev # curr is None; prev is the new head
print(to_list(reverse_list(build_list([1, 2, 3, 4, 5]))))
print(to_list(reverse_list(build_list([1]))))
print(to_list(reverse_list(build_list([]))))[5, 4, 3, 2, 1]
[1]
[]What happens without the save, which is worth demonstrating:
def reverse_broken(head):
prev, curr = None, head
steps = 0
while curr and steps < 10:
curr.next = prev # destroys the link to the rest
prev, curr = curr, curr.next # curr.next is now prev — we go backwards
steps += 1
return prev
result = reverse_broken(build_list([1, 2, 3, 4, 5]))
print(f"broken reversal returns: {to_list(result)} (lost 3 nodes)")broken reversal returns: [1] (lost 3 nodes)“
curr.next = prevoverwrites the only pointer to the remainder of the list. Savingnxtfirst is not defensive coding, it is the algorithm — that is why it is three pointers and not two.”
Recursive reversal is worth knowing as a contrast:
def reverse_recursive(head):
if not head or not head.next:
return head
new_head = reverse_recursive(head.next) # reverse the rest first
head.next.next = head # the node after me should point back at me
head.next = None # and I become the tail
return new_head
print(to_list(reverse_recursive(build_list([1, 2, 3, 4, 5]))))[5, 4, 3, 2, 1]Elegant, and O(n) stack space against the iterative version’s O(1). Say that: on a 100,000-node list the recursive version crashes and the iterative one does not.
The dummy head
def remove_all(head, target):
dummy = ListNode(0, head) # so removing the first node needs no special case
prev = dummy
while prev.next:
if prev.next.val == target:
prev.next = prev.next.next
else:
prev = prev.next
return dummy.next
print(to_list(remove_all(build_list([1, 2, 6, 3, 6, 4, 5, 6]), 6)))
print(to_list(remove_all(build_list([6, 6, 6]), 6)))
print(to_list(remove_all(build_list([]), 6)))[1, 2, 3, 4, 5]
[]
[]The [6, 6, 6] case is the one the dummy head earns its place on — every node removed,
including the head, with no branch for it.
Merging two sorted lists uses the same trick:
def merge_sorted(a, b):
dummy = tail = ListNode()
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b # attach whatever remains — no loop needed
return dummy.next
print(to_list(merge_sorted(build_list([1, 3, 5]), build_list([2, 4, 6]))))
print(to_list(merge_sorted(build_list([]), build_list([1, 2]))))[1, 2, 3, 4, 5, 6]
[1, 2]tail.next = a or b is the Python idiom worth using — at most one is non-None.
Trees: the four traversals
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
# 4
# / \
# 2 6
# / \ / \
# 1 3 5 7
root = TreeNode(4,
TreeNode(2, TreeNode(1), TreeNode(3)),
TreeNode(6, TreeNode(5), TreeNode(7)))
def inorder(node): return inorder(node.left) + [node.val] + inorder(node.right) if node else []
def preorder(node): return [node.val] + preorder(node.left) + preorder(node.right) if node else []
def postorder(node): return postorder(node.left) + postorder(node.right) + [node.val] if node else []
def levelorder(node):
if not node: return []
out, q = [], deque([node])
while q:
n = q.popleft()
out.append(n.val)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
return out
print(f"in-order {inorder(root)} ← sorted, for a BST")
print(f"pre-order {preorder(root)} ← root first: copy/serialise")
print(f"post-order {postorder(root)} ← children first: delete, compute height")
print(f"level-order {levelorder(root)} ← BFS: depth, per-level questions")in-order [1, 2, 3, 4, 5, 6, 7] ← sorted, for a BST
pre-order [4, 2, 1, 3, 6, 5, 7] ← root first: copy/serialise
post-order [1, 3, 2, 5, 7, 6, 4] ← children first: delete, compute height
level-order [4, 2, 6, 1, 3, 5, 7] ← BFS: depth, per-level questionsIn-order on a BST gives sorted output — that single fact answers a surprising number of questions, including “validate a BST” and “k-th smallest”.
The choice matters when a node’s answer depends on its children:
def height(node):
"""Post-order: I cannot know my height until I know my children's."""
return 0 if not node else 1 + max(height(node.left), height(node.right))
def is_balanced(node):
def check(n):
if not n: return 0
lh = check(n.left)
if lh == -1: return -1
rh = check(n.right)
if rh == -1: return -1
return -1 if abs(lh - rh) > 1 else 1 + max(lh, rh)
return check(node) != -1
print(f"height {height(root)} balanced {is_balanced(root)}")
skewed = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))))
print(f"skewed: height {height(skewed)} balanced {is_balanced(skewed)}")height 3 balanced True
skewed: height 4 balanced FalseThe -1 sentinel short-circuits — once any subtree is unbalanced, the rest is not explored.
The naive version calling height() inside the balance check is O(n²); this is O(n), and
saying so is the follow-up.
Level-order, kept per level
def levels(node):
if not node: return []
out, q = [], deque([node])
while q:
size = len(q) # snapshot: everything currently queued is this level
level = []
for _ in range(size):
n = q.popleft()
level.append(n.val)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
out.append(level)
return out
print(levels(root))
def right_side_view(node):
return [level[-1] for level in levels(node)]
print(f"right side view: {right_side_view(root)}")[[4], [2, 6], [1, 3, 5, 7]]
right side view: [4, 6, 7]size = len(q) taken before the inner loop is the whole technique — it separates levels
without storing depth on each node.
Validating a BST — the bounds trap
def is_bst_wrong(node):
"""Only checks parent-child, not the whole subtree."""
if not node: return True
if node.left and node.left.val >= node.val: return False
if node.right and node.right.val <= node.val: return False
return is_bst_wrong(node.left) and is_bst_wrong(node.right)
def is_bst(node, low=float("-inf"), high=float("inf")):
if not node: return True
if not (low < node.val < high): return False
return is_bst(node.left, low, node.val) and is_bst(node.right, node.val, high)
# 5
# / \
# 1 6
# / \
# 4 7 ← 4 is in the right subtree of 5 but less than 5
tricky = TreeNode(5, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7)))
print(f"local check only: {is_bst_wrong(tricky)} ← wrong")
print(f"with bounds: {is_bst(tricky)}")
print(f"valid tree: {is_bst(root)}")local check only: True ← wrong
with bounds: False
valid tree: True“Checking only parent against child is the classic mistake. A node deep in the right subtree must still be greater than every ancestor it descends from on a left branch — so the constraint is a range that narrows as you descend, not a single comparison.”
Lowest common ancestor
def lca(node, p, q):
"""Post-order: if p and q are found in different subtrees, this node is the LCA."""
if not node or node.val == p or node.val == q:
return node
left = lca(node.left, p, q)
right = lca(node.right, p, q)
if left and right:
return node # split here
return left or right # both on one side
print(f"LCA(1, 3) = {lca(root, 1, 3).val}")
print(f"LCA(1, 7) = {lca(root, 1, 7).val}")
print(f"LCA(5, 7) = {lca(root, 5, 7).val}")LCA(1, 3) = 2
LCA(1, 7) = 4
LCA(5, 7) = 6For a BST it is simpler — walk down while both targets are on the same side:
def lca_bst(node, p, q):
while node:
if p < node.val and q < node.val: node = node.left
elif p > node.val and q > node.val: node = node.right
else: return node # split point, or one of them
return None
print(f"BST LCA(1, 3) = {lca_bst(root, 1, 3).val} O(h), no recursion")BST LCA(1, 3) = 2 O(h), no recursionAsking whether the tree is a BST before answering is worth a mark — the answers differ.
The recursion depth problem
print(f"recursion limit: {sys.getrecursionlimit()}")
deep = TreeNode(0)
node = deep
for i in range(1, 5_000):
node.right = TreeNode(i)
node = node.right
try:
height(deep)
except RecursionError:
print("height(skewed 5000-node tree) → RecursionError")
def height_iterative(root):
if not root: return 0
best, stack = 0, [(root, 1)]
while stack:
node, d = stack.pop()
best = max(best, d)
if node.left: stack.append((node.left, d + 1))
if node.right: stack.append((node.right, d + 1))
return best
print(f"iterative height: {height_iterative(deep)}")recursion limit: 1000
height(skewed 5000-node tree) → RecursionError
iterative height: 5000“A balanced tree of a million nodes is only 20 deep, so recursion is fine. A skewed tree — which is what you get from inserting sorted data into an unbalanced BST — is n deep, and Python’s limit is 1000. If the input could be skewed I would write it iteratively rather than raise the limit, because raising it trades a clean exception for a segfault.”
Mentioning this unprompted is a strong signal, because it is a real production failure and not just an interview technicality.
Iterative in-order, for when you need it
def inorder_iterative(root):
out, stack, node = [], [], root
while stack or node:
while node: # go as far left as possible
stack.append(node)
node = node.left
node = stack.pop()
out.append(node.val)
node = node.right # then one step right, and repeat
return out
print(inorder_iterative(root))[1, 2, 3, 4, 5, 6, 7]The explicit stack mirrors exactly what recursion was doing implicitly, which is the way to explain it.
Recognising it
SIGNAL REACH FOR
"reverse", "reorder" a linked list three pointers
operation may affect the head dummy head node
cycle, middle, k-th from end fast/slow pointers
"sorted output" from a BST in-order traversal
"validate a BST" in-order, or bounds passed down
node's answer depends on children post-order
"level", "depth", "each row" BFS with a level-size snapshot
"lowest common ancestor" post-order (BST: walk down)
"serialise / copy the tree" pre-order
tree could be skewed and large iterative, explicit stackThe checklist
print(to_list(reverse_list(None)))
print(inorder(None), levels(None))
print(is_bst(None), height(None))
print(to_list(merge_sorted(None, None)))
print(lca(root, 4, 1).val, " ← target is the root itself")[]
[] []
True 0
[]
4 ← target is the root itselfEmpty tree, empty list, and the target-is-the-root case are the three that break these solutions.
Practice
1. Reverse a list without saving the next pointer.
broken reversal returns: [1] (lost 3 nodes)curr.next = prev destroys the only reference to the remainder. The save is the algorithm, not
defensive style.
2. Validate a BST with a parent-child check only.
local check only: True ← wrong
with bounds: FalseA node in the right subtree can be smaller than an ancestor. The constraint is a narrowing range, which is the insight the question tests.
3. Recurse on a 5,000-node skewed tree.
RecursionError (limit 1000)Balanced trees are fine; skewed ones are not, and sorted input into an unbalanced BST produces exactly that. Say it before being asked.
4. Remove every node from a list using a dummy head.
remove_all([6,6,6], 6) → []No special case for the head. Without the dummy, deleting the first node needs its own branch — which is where the off-by-one lives.
Next: graphs — BFS, DFS, topological order, and the shortest-path question.