Distance Problems in Binary Trees

Distance problems in binary trees ask you to compute how “far apart” nodes are. Unlike graphs, trees have a unique path between any two nodes, so the distance is always well-defined. But computing it efficiently requires clever techniques — from LCA-based formulas to rerooting dynamic programming.

---

TreeNode Definition

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

---

Problem 1: Distance Between Two Nodes

Given a binary tree and two node values, find the number of edges on the path between them.

        1
       / \
      2   3
     / \
    4   5

Distance(4, 5) = 2  (4 → 2 → 5)
Distance(4, 3) = 3  (4 → 2 → 1 → 3)

Approach: LCA + Depth

The distance between nodes a and b is:

dist(a, b) = depth(a) + depth(b) - 2 * depth(LCA(a, b))

def find_distance(root, p, q):
    """Find distance between nodes with values p and q."""

    def lca(node, p, q):
        """Find lowest common ancestor."""
        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
        return left or right

    def depth_from(node, target, d):
        """Find depth of target starting from node."""
        if not node:
            return -1
        if node.val == target:
            return d
        left = depth_from(node.left, target, d + 1)
        if left != -1:
            return left
        return depth_from(node.right, target, d + 1)

    ancestor = lca(root, p, q)
    d1 = depth_from(ancestor, p, 0)
    d2 = depth_from(ancestor, q, 0)
    return d1 + d2

Single-pass approach

We can also compute the distance in a single DFS pass:

def find_distance_single_pass(root, p, q):
    """Find distance between p and q in one DFS pass."""
    result = [0]

    def dfs(node):
        if not node:
            return -1

        left = dfs(node.left)
        right = dfs(node.right)

        if node.val == p or node.val == q:
            # If one target is in a subtree, distance is that depth
            if left != -1:
                result[0] = left + 1
                return 0  # Reset distance from this node
            if right != -1:
                result[0] = right + 1
                return 0
            return 0  # Found a target, distance from here is 0

        if left != -1 and right != -1:
            # Both targets found in different subtrees — this is LCA
            result[0] = left + right + 2
            return -1  # Signal: both found

        if left != -1:
            return left + 1
        if right != -1:
            return right + 1

        return -1  # Neither target found

    dfs(root)
    return result[0]

Complexity

Metric	Value
Time	O(n)
Space	O(h) — recursion stack

---

Problem 2: All Nodes at Distance K

LeetCode 863. Given a binary tree, a target node, and an integer K, return all nodes that are distance K from the target.

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

Target = 5, K = 2
Answer: [7, 4, 1]

Nodes at distance 2 from 5: go down 2 to get 7 and 4, or go up to 3 then down to 1.

Approach: Convert tree to graph, then BFS

The key insight: in a tree, nodes can only go to their children. But distance K may require going upward through the parent. So we build a parent map and treat the tree as an undirected graph.

from collections import deque

def distance_k(root, target, k):
    """Find all nodes at distance K from target."""
    # Step 1: Build parent map
    parent = {}

    def build_parent(node, par=None):
        if not node:
            return
        parent[node] = par
        build_parent(node.left, node)
        build_parent(node.right, node)

    build_parent(root)

    # Step 2: BFS from target
    queue = deque([(target, 0)])
    visited = {target}
    result = []

    while queue:
        node, dist = queue.popleft()

        if dist == k:
            result.append(node.val)
            continue  # No need to go further

        if dist > k:
            break

        # Explore neighbors: left, right, parent
        neighbors = [node.left, node.right, parent[node]]
        for neighbor in neighbors:
            if neighbor and neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return result

Alternative: Pure DFS without parent map

def distance_k_dfs(root, target, k):
    """Find nodes at distance K using DFS only (no parent map)."""
    result = []

    def collect_downward(node, dist):
        """Collect all nodes at distance dist going downward."""
        if not node or dist < 0:
            return
        if dist == 0:
            result.append(node.val)
            return
        collect_downward(node.left, dist - 1)
        collect_downward(node.right, dist - 1)

    def dfs(node):
        """Returns distance from node to target, or -1 if target not in subtree."""
        if not node:
            return -1

        if node == target:
            # Collect all nodes at distance K downward
            collect_downward(node, k)
            return 0

        left_dist = dfs(node.left)
        if left_dist != -1:
            # Target is in left subtree
            if left_dist + 1 == k:
                result.append(node.val)
            else:
                # Look in right subtree for remaining distance
                collect_downward(node.right, k - left_dist - 2)
            return left_dist + 1

        right_dist = dfs(node.right)
        if right_dist != -1:
            if right_dist + 1 == k:
                result.append(node.val)
            else:
                collect_downward(node.left, k - right_dist - 2)
            return right_dist + 1

        return -1

    dfs(root)
    return result

Complexity

Metric	Value
Time	O(n)
Space	O(n) — parent map or recursion

---

Problem 3: Burn a Binary Tree from a Node

Given a binary tree and a starting node, “burn” the tree. Each second, fire spreads to all adjacent nodes (children and parent). Find the time to burn the entire tree.

This is equivalent to finding the farthest node from the starting node — the diameter measured from one point.

        1
       / \
      2   3
     / \
    4   5

Start burning from node 2.
t=0: burn 2
t=1: burn 4, 5, 1
t=2: burn 3

Total time: 2

Approach: BFS from start node with parent pointers

from collections import deque

def burn_tree(root, start_val):
    """Find time to burn entire tree starting from start_val."""
    # Build parent map and find start node
    parent = {}
    start_node = None

    def build(node, par=None):
        nonlocal start_node
        if not node:
            return
        if node.val == start_val:
            start_node = node
        parent[node] = par
        build(node.left, node)
        build(node.right, node)

    build(root)

    # BFS — each level = one second
    queue = deque([start_node])
    visited = {start_node}
    time = -1  # Start at -1 so first level is t=0

    while queue:
        time += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            neighbors = [node.left, node.right, parent.get(node)]
            for neighbor in neighbors:
                if neighbor and neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

    return time

Alternative: DFS approach

def burn_tree_dfs(root, start_val):
    """Find burn time using DFS — returns max distance from start."""
    max_time = [0]

    def dfs(node):
        """Returns distance from this node to start, or -1 if start not in subtree."""
        if not node:
            return -1

        if node.val == start_val:
            # Compute height of subtree rooted at start
            def height(n):
                if not n:
                    return -1
                return 1 + max(height(n.left), height(n.right))

            max_time[0] = max(max_time[0], height(node))
            return 0

        left = dfs(node.left)
        right = dfs(node.right)

        if left != -1:
            # Start is in left subtree
            # Fire reaches right subtree after left+1 steps, then needs height(right) more
            right_height = height_of(node.right)
            max_time[0] = max(max_time[0], left + 2 + right_height)
            return left + 1

        if right != -1:
            left_height = height_of(node.left)
            max_time[0] = max(max_time[0], right + 2 + left_height)
            return right + 1

        return -1

    def height_of(node):
        if not node:
            return -1
        return 1 + max(height_of(node.left), height_of(node.right))

    dfs(root)
    return max_time[0]

Complexity

Metric	Value
Time	O(n)
Space	O(n)

---

Problem 4: Sum of Distances in Tree (Rerooting)

LeetCode 834. Given a tree with n nodes (0 to n-1), return an array where answer[i] is the sum of distances from node i to all other nodes.

Tree edges: [[0,1],[0,2],[2,3],[2,4],[2,5]]

        0
       / \
      1   2
         /|\
        3 4 5

answer[0] = 1+1+2+2+2 = 8
answer[2] = 2+1+1+1+1 = 6

Naive approach: BFS from each node — O(n^2)

from collections import defaultdict, deque

def sum_of_distances_naive(n, edges):
    """O(n^2) approach — BFS from every node."""
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    result = [0] * n

    for start in range(n):
        visited = {start}
        queue = deque([(start, 0)])
        while queue:
            node, dist = queue.popleft()
            result[start] += dist
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, dist + 1))

    return result

Optimal approach: Rerooting DP — O(n)

The rerooting technique uses two DFS passes:

1. First DFS (root at 0): Compute count[i] (subtree size) and dist_sum[0] (sum of distances from node 0).
2. Second DFS: When we “move the root” from parent to child, the distances change predictably.

When we move root from parent to child:

• All nodes in child’s subtree get 1 closer (there are count[child] of them)
• All other nodes get 1 farther (there are n - count[child] of them)

So: answer[child] = answer[parent] - count[child] + (n - count[child])

from collections import defaultdict

def sum_of_distances(n, edges):
    """O(n) rerooting approach."""
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    count = [1] * n   # Subtree size (including self)
    answer = [0] * n

    # DFS 1: Compute subtree sizes and answer[0]
    def dfs1(node, parent):
        for child in graph[node]:
            if child != parent:
                dfs1(child, node)
                count[node] += count[child]
                answer[0] += count[child]  # Each node in subtree adds 1 to distance

    dfs1(0, -1)

    # DFS 2: Reroot — compute answer for all nodes
    def dfs2(node, parent):
        for child in graph[node]:
            if child != parent:
                answer[child] = answer[node] - count[child] + (n - count[child])
                dfs2(child, node)

    dfs2(0, -1)

    return answer

Why the formula works

When rerooting from parent to child:

  answer[child] = answer[parent]
                  - count[child]       (these nodes get closer by 1)
                  + (n - count[child]) (these nodes get farther by 1)

Complexity

Metric	Value
Time	O(n) — two DFS passes
Space	O(n) — graph + arrays

This is a dramatic improvement over the naive O(n^2) approach.

---

Problem 5: Diameter Passing Through a Given Node

Find the longest path in the tree that passes through a specific node.

def diameter_through_node(root, target_val):
    """Find the longest path passing through a specific node."""
    result = [0]

    def height(node):
        if not node:
            return -1
        return 1 + max(height(node.left), height(node.right))

    def find_and_compute(node):
        if not node:
            return False

        if node.val == target_val:
            left_h = height(node.left)
            right_h = height(node.right)
            # Diameter through this node
            result[0] = left_h + right_h + 2
            return True

        return find_and_compute(node.left) or find_and_compute(node.right)

    find_and_compute(root)
    return result[0]

---

Kth Ancestor of a Node

A useful building block: find the kth ancestor of a given node.

def kth_ancestor(root, target_val, k):
    """Find the kth ancestor of the target node."""
    path = []

    def find_path(node):
        if not node:
            return False
        path.append(node)
        if node.val == target_val:
            return True
        if find_path(node.left) or find_path(node.right):
            return True
        path.pop()
        return False

    find_path(root)

    if len(path) {'<'} k + 1:
        return -1  # Kth ancestor doesn't exist

    return path[-(k + 1)].val

---

Comparison of Approaches

Problem	Key Technique	Time	Space
Distance between 2 nodes	LCA + depth	O(n)	O(h)
All nodes at distance K	Parent map + BFS	O(n)	O(n)
Burn binary tree	Parent map + BFS	O(n)	O(n)
Sum of distances	Rerooting DP	O(n)	O(n)

---

Common Mistakes

1. Forgetting to go upward — distance K problems require traversing to parent nodes, not just children. Without a parent map, you miss solutions above the target.

2. Not tracking visited nodes — when BFS-ing through parent pointers, you can revisit nodes. Always use a visited set.

3. Rerooting formula errors — the formula answer[child] = answer[parent] - count[child] + (n - count[child]) only works on unweighted trees. For weighted trees, multiply by edge weights.

4. Off-by-one in burn time — remember that the starting node burns at t=0, not t=1.

---

Practice Problems

Problem	Platform	Difficulty
All Nodes Distance K in Binary Tree	LeetCode 863	Medium
Sum of Distances in Tree	LeetCode 834	Hard
Closest Leaf in a Binary Tree	LeetCode 742	Medium
Amount of Time for Binary Tree to Be Infected	LeetCode 2385	Medium
Find Distance in a Binary Tree	LeetCode 1740	Medium

---

Key Takeaways

• LCA is the foundation for distance calculations: dist(a,b) = depth(a) + depth(b) - 2*depth(LCA).
• Parent map + BFS turns any tree into an undirected graph, enabling “go upward” traversals.
• Rerooting DP solves “sum of distances from every node” in O(n) instead of O(n^2) — a must-know technique for competitive programming.
• The burn tree problem is just BFS on a tree with parent pointers — recognizing it as a graph problem is the key insight.
• Distance problems often combine multiple techniques: LCA + DFS, parent map + BFS, or subtree counts + rerooting.