LeetCode Solutions Blog

Find Distance in a Binary Tree

Number: 1883

Difficulty: Medium

Paid? Yes

Problem Description

Given the root of a binary tree and two integers p and q (which are values guaranteed to exist in the tree), return the distance between the nodes with value p and value q. The distance is defined as the number of edges along the path connecting the two nodes. If p equals q, the distance is 0.

Key Insights

The problem can be effectively solved by first finding the Lowest Common Ancestor (LCA) of the two nodes.
Once the LCA is located, the distance between the two nodes is the sum of the distance from the LCA to p and from the LCA to q.
Depth-first search (DFS) is used both to find the LCA and to compute the distance from the LCA to each node.

Space and Time Complexity

Time Complexity: O(n) in the worst-case, where n is the number of nodes in the tree. Space Complexity: O(h), where h is the height of the tree (due to recursion stack).

Solution

We first determine the Lowest Common Ancestor (LCA) of the nodes with values p and q. To do this, we recursively check the left and right subtrees until we find either p or q. Once the LCA is found, we perform a DFS from the LCA to calculate the distance (number of edges) to each target value. The final distance between p and q is the sum of these two distances. Edge cases such as p == q are handled by simply returning a distance of 0.

Code Solutions

# 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

# Function to find the Lowest Common Ancestor (LCA) of two nodes with values target1 and target2.
def findLCA(root, target1, target2):
    if not root:
        return None
    # If current node is one of the targets, return it.
    if root.val == target1 or root.val == target2:
        return root
    # Recurse on left and right subtrees.
    left = findLCA(root.left, target1, target2)
    right = findLCA(root.right, target1, target2)
    # If both sides return non-None, the current node is the LCA.
    if left and right:
        return root
    # Otherwise, return the side that is non-None.
    return left if left else right

# Function to find the distance from node to target value using DFS.
def findDistanceFromNode(root, target, current_distance):
    if not root:
        return -1  # target not found in this branch.
    if root.val == target:
        return current_distance
    left_distance = findDistanceFromNode(root.left, target, current_distance + 1)
    if left_distance != -1:
        return left_distance
    return findDistanceFromNode(root.right, target, current_distance + 1)

def findDistance(root, p, q):
    # If both values are the same, distance is zero.
    if p == q:
        return 0
    # First, find the Lowest Common Ancestor of nodes with values p and q.
    lca = findLCA(root, p, q)
    # Then, find the distance from the LCA to p and q respectively.
    distance_p = findDistanceFromNode(lca, p, 0)
    distance_q = findDistanceFromNode(lca, q, 0)
    # The distance between p and q is the sum of the two distances.
    return distance_p + distance_q