Path Sum and Lowest Common Ancestor
Solve root-to-leaf path sum, all-paths-sum, and lowest-common-ancestor for a general binary tree using recursive descent.
Path Sum and Lowest Common Ancestor is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Root-to-Leaf Path Sum
The path sum problem asks whether any root-to-leaf path sums to a target. Pass the remaining target down the recursion, subtracting each node's value. At a leaf, check if the remaining equals the leaf's value. This avoids maintaining an explicit path list and is both space-efficient and clean. Edge case: an empty tree has no paths, so return False immediately.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def has_path_sum(root, target):
if not root:
return False
if not root.left and not root.right: # leaf
return root.val == target
remain = target - root.val
return (has_path_sum(root.left, remain) or
has_path_sum(root.right, remain))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5->4->11->2All Root-to-Leaf Paths
To enumerate all paths, maintain a running path list. At each recursive call, append the current node's value, recurse into children, then pop on return (backtrack). At a leaf, record a snapshot (list(path)) of the current path. This pattern — choose, recurse, unchoose — is the foundation of backtracking on trees.
def all_path_sums(root, target):
results = []
def dfs(node, path, remaining):
if not node:
return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
results.append(list(path)) # snapshot
else:
dfs(node.left, path, remaining - node.val)
dfs(node.right, path, remaining - node.val)
path.pop() # backtrack
dfs(root, [], target)
return results
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(5)
print(all_path_sums(root, 22)) # [[5,4,11,2]]Path Sum III: Any Path, Any Node
Path Sum III (LeetCode #437) counts paths that sum to a target where the path can start and end anywhere (not just root-to-leaf). The brute-force is O(n²): run a DFS from every node. The optimal O(n) approach uses a prefix sum hash map: track the running sum and count how many times current_sum - target appeared before, mirroring the subarray sum approach.
def path_sum_iii(root, target):
prefix_counts = {0: 1}
def dfs(node, running_sum):
if not node:
return 0
running_sum += node.val
count = prefix_counts.get(running_sum - target, 0)
prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
count += dfs(node.left, running_sum)
count += dfs(node.right, running_sum)
prefix_counts[running_sum] -= 1 # backtrack
return count
return dfs(root, 0)
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(-3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.right = TreeNode(11)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(-2)
root.left.right.right = TreeNode(1)
print(path_sum_iii(root, 8)) # 3What is the Lowest Common Ancestor?
The Lowest Common Ancestor (LCA) of two nodes p and q in a binary tree is the deepest node that has both p and q as descendants (a node can be a descendant of itself). LCA appears in problems like 'distance between two nodes', 'path between two nodes', and BST range queries. Understanding LCA is essential for intermediate tree problems.
# 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
# LCA(5, 1) = 3 (root)
# LCA(5, 4) = 5 (p itself is ancestor of q)
# LCA(6, 4) = 5
# LCA(7, 4) = 2
# Key insight: the LCA is the node where p and q
# first 'split' into different subtrees.
print('LCA: deepest node that is ancestor of both p and q')LCA Recursive Algorithm
The elegant recursive LCA solution returns the first node that is either p or q, or has both in its subtrees. If the current node is p or q, return it. Otherwise, recurse left and right. If both sides return non-null, the current node is the LCA. If only one side is non-null, propagate that result upward. This runs in O(n) time and O(h) space.
def lowest_common_ancestor(root, p, q):
# Base case: empty or found one of the targets
if not root or root == p or root == q:
return root
# Search both subtrees
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
# If both sides found something, this node is the LCA
if left and right:
return root
# Otherwise, return whichever side found something
return left if left else right
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
p, q = root.left, root.right # 5 and 1
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 3LCA When a Node Can Be Its Own Ancestor
A critical edge case: if p is an ancestor of q (or vice versa), the LCA is p itself. The recursive algorithm handles this automatically — when it reaches p, it returns p immediately without looking into p's subtrees. The parent will see that one side returned p and the other returned null, so it propagates p upward as the LCA. Always verify this case with your test when coding LCA.
# Test case: p is ancestor of q
# Tree: 3 -> left=5 -> left=6
# LCA(5, 6) should be 5
root = TreeNode(3)
root.left = TreeNode(5)
root.left.left = TreeNode(6)
p = root.left # node 5
q = root.left.left # node 6
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 5 (p itself is the LCA)LCA with Parent Pointers
If each node has a parent pointer, LCA reduces to the 'intersection of two linked lists' problem. Collect ancestors of p in a set, then walk up from q until you find a node in that set. This O(h) time and O(h) space approach is common in system design interviews where you control the node structure and can store parent references.
class NodeWithParent:
def __init__(self, val, parent=None):
self.val = val
self.parent = parent
self.left = None
self.right = None
def lca_with_parent(p, q):
ancestors = set()
# Collect all ancestors of p
node = p
while node:
ancestors.add(node)
node = node.parent
# Walk up from q until we hit a known ancestor
node = q
while node:
if node in ancestors:
return node
node = node.parent
return None
print('With parent pointers: O(h) time and space')LCA in a Binary Search Tree
In a BST, LCA is simpler because the ordering property tells you which subtree contains each node. If both p and q are smaller than the current node, LCA is in the left subtree. If both are larger, LCA is in the right subtree. Otherwise, the current node splits them, so it is the LCA. This reduces the problem to O(log n) for balanced BSTs.
def lca_bst(root, p, q):
if not root:
return None
if p.val < root.val and q.val < root.val:
return lca_bst(root.left, p, q) # both in left
if p.val > root.val and q.val > root.val:
return lca_bst(root.right, p, q) # both in right
return root # split point = LCA
# Iterative BST LCA (no recursion overhead):
def lca_bst_iter(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 root
return None
print('BST LCA: O(log n) for balanced trees')Distance Between Two Nodes
The distance between two nodes in a tree equals the number of edges on the path connecting them. This is directly computed from the LCA: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Find the LCA first, then count the depth of each node. With a proper helper, this runs in O(n) time and O(h) space.
def find_depth(root, target, depth=0):
if not root:
return -1
if root == target:
return depth
left = find_depth(root.left, target, depth + 1)
if left != -1:
return left
return find_depth(root.right, target, depth + 1)
def node_distance(root, p, q):
lca = lowest_common_ancestor(root, p, q)
# depth from LCA to p and q
dp = find_depth(lca, p)
dq = find_depth(lca, q)
return dp + dq
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(node_distance(root, root.left.left, root.left.right)) # 2Maximum Sum Root-to-Leaf Path
The maximum sum root-to-leaf path tracks the running sum from root to the current node. At leaves, compare against a global maximum. This is a pre-order DFS where the current-path-sum is passed as a parameter. Unlike the generic maximum path sum, this version is constrained to root-to-leaf paths, so it is simpler — no need to consider arbitrary node-to-node paths.
def max_root_to_leaf_sum(root):
if not root:
return float('-inf')
best = [float('-inf')]
def dfs(node, running):
running += node.val
if not node.left and not node.right: # leaf
best[0] = max(best[0], running)
return
if node.left:
dfs(node.left, running)
if node.right:
dfs(node.right, running)
dfs(root, 0)
return best[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(max_root_to_leaf_sum(root)) # 1+2+5 = 8Sum Root to Leaf Numbers
Sum root-to-leaf numbers (LeetCode #129) treats each root-to-leaf path as a decimal number (e.g., path 1→2→3 represents the number 123) and asks for their sum. Build the number by passing current_number * 10 + node.val down the recursion. At each leaf, add the completed number to the total. This is a clean example of pre-order DFS passing accumulated state downward.
def sum_numbers(root):
def dfs(node, num):
if not node:
return 0
num = num * 10 + node.val
if not node.left and not node.right: # leaf
return num
return dfs(node.left, num) + dfs(node.right, num)
return dfs(root, 0)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(sum_numbers(root)) # 12 + 13 = 25
root2 = TreeNode(4)
root2.left = TreeNode(9)
root2.right = TreeNode(0)
root2.left.left = TreeNode(5)
root2.left.right = TreeNode(1)
print(sum_numbers(root2)) # 495 + 491 + 40 = 1026Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: path sum variants (root-to-leaf, all paths, path sum III with prefix sums), lowest common ancestor using elegant recursive splitting, and BST LCA in O(log n) using the ordering property. Next up we start Binary Search Trees with insert and search operations.
Frequently asked questions
Is the “Path Sum and Lowest Common Ancestor” lesson free?
Yes — the full text of “Path Sum and Lowest Common Ancestor” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Path Sum and Lowest Common Ancestor”?
Solve root-to-leaf path sum, all-paths-sum, and lowest-common-ancestor for a general binary tree using recursive descent. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Path Sum and Lowest Common Ancestor” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- TreeNode Class and Level-Order BFS
- In-Order, Pre-Order, Post-Order DFS
- Diameter, Height, and Balanced Trees
- Path Sum and Lowest Common Ancestor