Distance between two nodes in a Binary Tree

Given the root of a Binary Tree and 2 integers that represent the data values of any two TreeNodes present in the tree, write a method - getNodeDistance that returns the distance between the nodes. You can assume that the given keys exist in the tree. The distance between two nodes is defined as the minimum number of edges that must be traversed to travel between the two nodes.

Example:

       1
      / \
     2   3
      \   \     
       4   5

getNodeDistance(2,5) => 3

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

By now you should know how to find the LCA or Lowest Common Ancestor of two nodes in a binary tree, as well as the path length between a given node and the root. We are going to simplify this problem by solving smaller subproblems and combining the result using the following formula :

Note:

pathLen(Root,B) = Distance between the root and node B

lca(A,B) = Lowest Common Ancestor of nodes A and B

Formula :
getNodeDistance(A,B) = pathLen(Root, A) + pathLen(Root, B) - (2 * pathLen(Root, lca(A,B)))

public int getNodeDistance(TreeNode root, int n1, int n2) {
    
}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Distance between two nodes in a Binary Tree

Quick hint to get things rolling

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :