1740. Find Distance in a Binary Tree - Leetcode Solution

Problem Description

Given the root of a binary tree, and two integer values p and q representing two distinct nodes in the tree, your task is to find the number of edges in the shortest path between the nodes with values p and q.

Each node has a unique value.
You are guaranteed that both p and q exist in the tree.
The binary tree is not necessarily a binary search tree.

The output should be an integer representing the distance (in number of edges) between the two nodes.

Thought Process

At first glance, it might seem like you need to search from one node to the other, but since the tree is undirected (you can move up or down), the shortest path between two nodes always goes through their lowest common ancestor (LCA).

The brute-force idea would be to find the path from the root to p and from the root to q, then compare the paths to find where they diverge (their LCA). The sum of the unique edges from the LCA to each node gives the answer.

However, a more optimized approach is to:

Find the LCA of p and q.
Compute the distance from the LCA to p and from the LCA to q.
Add these two distances together for the result.

This avoids storing full paths and is more efficient.

Solution Approach

Here's how to solve the problem step-by-step:

Find the Lowest Common Ancestor (LCA):
- Traverse the tree recursively.
- If the current node matches either p or q, return the node.
- Recursively search the left and right subtrees.
- If both sides return non-null, the current node is the LCA.
- If only one side is non-null, propagate it up.
Compute the Distance from LCA to Each Node:
- Use a helper function to traverse from the LCA to p, counting edges.
- Repeat for q.
- Return the sum of these two distances.
Why This Works:
- The shortest path between p and q in a tree is always via their LCA.
- By counting the edges from LCA to each node, we avoid unnecessary repeated traversals.

This approach is efficient, intuitive, and leverages the properties of trees.

Example Walkthrough

Consider this tree:

Suppose p = 4 and q = 5.

Find LCA:
- Both 4 and 5 are in the left subtree of 2. Their LCA is 2.
Find distance from 2 to 4: 1 edge (2 - 4)
Find distance from 2 to 5: 1 edge (2 - 5)
Total distance: 1 + 1 = 2

The shortest path between node 4 and node 5 is 2 edges: 4 - 2 - 5.

Time and Space Complexity

Brute-force approach:
- Finding root-to-node paths for both p and q takes O(N) time each, where N is the number of nodes.
- Comparing paths is O(N).
- Total time: O(N)
- Space: O(N) for storing paths.
Optimized approach (LCA + distances):
- Finding the LCA is O(N).
- Finding distance from LCA to p and q is O(N) in the worst case, but usually much less.
- Total time: O(N)
- Space: O(H), where H is the height of the tree (due to recursion stack).

Both approaches are linear in the number of nodes, but the optimized approach is more memory-efficient.

Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findDistance(self, root: TreeNode, p: int, q: int) -> int:
        def lca(node):
            if not node or node.val == p or node.val == q:
                return node
            left = lca(node.left)
            right = lca(node.right)
            if left and right:
                return node
            return left or right

        def distance(node, target, d):
            if not node:
                return -1
            if node.val == target:
                return d
            left = distance(node.left, target, d+1)
            if left != -1:
                return left
            return distance(node.right, target, d+1)

        ancestor = lca(root)
        return distance(ancestor, p, 0) + distance(ancestor, q, 0)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* lca(TreeNode* node, int p, int q) {
        if (!node || node->val == p || node->val == q)
            return node;
        TreeNode* left = lca(node->left, p, q);
        TreeNode* right = lca(node->right, p, q);
        if (left && right) return node;
        return left ? left : right;
    }
    int distance(TreeNode* node, int target, int d) {
        if (!node) return -1;
        if (node->val == target) return d;
        int left = distance(node->left, target, d+1);
        if (left != -1) return left;
        return distance(node->right, target, d+1);
    }
    int findDistance(TreeNode* root, int p, int q) {
        TreeNode* ancestor = lca(root, p, q);
        return distance(ancestor, p, 0) + distance(ancestor, q, 0);
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode lca(TreeNode node, int p, int q) {
        if (node == null || node.val == p || node.val == q)
            return node;
        TreeNode left = lca(node.left, p, q);
        TreeNode right = lca(node.right, p, q);
        if (left != null && right != null) return node;
        return left != null ? left : right;
    }

    private int distance(TreeNode node, int target, int d) {
        if (node == null) return -1;
        if (node.val == target) return d;
        int left = distance(node.left, target, d + 1);
        if (left != -1) return left;
        return distance(node.right, target, d + 1);
    }

    public int findDistance(TreeNode root, int p, int q) {
        TreeNode ancestor = lca(root, p, q);
        return distance(ancestor, p, 0) + distance(ancestor, q, 0);
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

var findDistance = function(root, p, q) {
    function lca(node) {
        if (!node || node.val === p || node.val === q) return node;
        let left = lca(node.left);
        let right = lca(node.right);
        if (left && right) return node;
        return left || right;
    }
    function distance(node, target, d) {
        if (!node) return -1;
        if (node.val === target) return d;
        let left = distance(node.left, target, d+1);
        if (left !== -1) return left;
        return distance(node.right, target, d+1);
    }
    let ancestor = lca(root);
    return distance(ancestor, p, 0) + distance(ancestor, q, 0);
};

Summary

To find the distance between two nodes in a binary tree, the most efficient strategy is to identify their lowest common ancestor (LCA) and sum the distances from the LCA to each node. This leverages tree properties and avoids unnecessary repeated traversals. The solution is elegant, intuitive, and runs in linear time with respect to the number of nodes, making it both practical and optimal for large trees.

AlgoMap.io

Want Help Cracking FAANG?