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.
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 :
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)))