Find the Distance Between Two Nodes in a Binary Tree

Algorithm Steps

Given a binary tree and two target node values.
Find the lowest common ancestor (LCA) of the two nodes.
Compute the distance from the LCA to the first node.
Compute the distance from the LCA to the second node.
The distance between the two nodes is the sum of these two distances.

Find the Distance Between Two Nodes in a Binary Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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

def lowestCommonAncestor(root, n1, n2):
    if not root or root.val == n1 or root.val == n2:
        return root
    left = lowestCommonAncestor(root.left, n1, n2)
    right = lowestCommonAncestor(root.right, n1, n2)
    if left and right:
        return root
    return left if left else right

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

def distanceBetweenNodes(root, n1, n2):
    lca = lowestCommonAncestor(root, n1, n2)
    d1 = distanceFromRoot(lca, n1, 0)
    d2 = distanceFromRoot(lca, n2, 0)
    return d1 + d2

if __name__ == '__main__':
    # Construct binary tree:
    #         1
    #        / \
    #       2   3
    #      / \   
    #     4   5  
    root = TreeNode(1)
    root.left = TreeNode(2, TreeNode(4), TreeNode(5))
    root.right = TreeNode(3)
    print(distanceBetweenNodes(root, 4, 5))  # Expected output: 2