Find Distance in a Binary Tree

medium tree lca dfs

Problem

Given the root of a binary tree and the values of two nodes p and q, return the distance between the two nodes. The distance is the number of edges on the path connecting them.

Inputroot = [1,2,3,4,5,6,7], p = 4, q = 6

Output4

Their lowest common ancestor is the root 1. Node 4 sits 2 edges below it and node 6 sits 2 edges below it, so the distance is 2 + 2 = 4.

level-order (use "null" for missing children)

def find_distance(root, p, q):
    def lca(node):
        if not node or node.val == p or node.val == q:
            return node
        L = lca(node.left)
        R = lca(node.right)
        if L and R:
            return node
        return L or R
    def depth(node, target):
        if not node:
            return -1
        if node.val == target:
            return 0
        d = depth(node.left, target)
        if d >= 0:
            return d + 1
        d = depth(node.right, target)
        return d + 1 if d >= 0 else -1
    a = lca(root)
    return depth(a, p) + depth(a, q)

function findDistance(root, p, q) {
  function lca(node) {
    if (!node || node.val === p || node.val === q) return node;
    const L = lca(node.left);
    const R = lca(node.right);
    if (L && R) return node;
    return L || R;
  }
  function depth(node, target) {
    if (!node) return -1;
    if (node.val === target) return 0;
    let d = depth(node.left, target);
    if (d >= 0) return d + 1;
    d = depth(node.right, target);
    return d >= 0 ? d + 1 : -1;
  }
  const a = lca(root);
  return depth(a, p) + depth(a, q);
}

class Solution {
    int p, q;
    public int findDistance(TreeNode root, int p, int q) {
        this.p = p; this.q = q;
        TreeNode a = lca(root);
        return depth(a, p) + depth(a, q);
    }
    TreeNode lca(TreeNode node) {
        if (node == null || node.val == p || node.val == q) return node;
        TreeNode L = lca(node.left), R = lca(node.right);
        if (L != null && R != null) return node;
        return L != null ? L : R;
    }
    int depth(TreeNode node, int target) {
        if (node == null) return -1;
        if (node.val == target) return 0;
        int d = depth(node.left, target);
        if (d >= 0) return d + 1;
        d = depth(node.right, target);
        return d >= 0 ? d + 1 : -1;
    }
}

class Solution {
public:
    int p, q;
    TreeNode* lca(TreeNode* node) {
        if (!node || node->val == p || node->val == q) return node;
        TreeNode* L = lca(node->left);
        TreeNode* R = lca(node->right);
        if (L && R) return node;
        return L ? L : R;
    }
    int depth(TreeNode* node, int target) {
        if (!node) return -1;
        if (node->val == target) return 0;
        int d = depth(node->left, target);
        if (d >= 0) return d + 1;
        d = depth(node->right, target);
        return d >= 0 ? d + 1 : -1;
    }
    int findDistance(TreeNode* root, int p_, int q_) {
        p = p_; q = q_;
        TreeNode* a = lca(root);
        return depth(a, p) + depth(a, q);
    }
};

Explanation

The path between any two nodes in a tree bends exactly once, at their lowest common ancestor (LCA) — the deepest node that has both p and q in its subtree. Once we know that meeting point, the distance is just how far each target sits below it.

To find the LCA we recurse down. A node returns itself if it is p or q. Otherwise it asks its left and right subtrees. If both sides report a match, this node is the split point, so it is the LCA. If only one side reports a match, we bubble that result upward.

With the LCA in hand, we run a simple depth search from it to p and another to q. Each returns the number of edges down to the target. Their sum is the answer because the two downward paths share no edges below the LCA.

If p and q are the same node the distance is 0, and if one is an ancestor of the other the LCA is that ancestor, so one of the two depths is 0.

Example on [1,2,3,4,5,6,7] with p = 4, q = 6: the LCA is the root 1. Node 4 is 2 edges down (1→2→4) and node 6 is 2 edges down (1→3→6), so the distance is 2 + 2 = 4.

Time: O(n) Space: O(h)