data
values of any two TreeNode
s 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. 1
/ \
2 3
\ \
4 5
getNodeDistance(2,5) => 3
pathLen(Root,B) = Distance between the root and node B
lca(A,B) = Lowest Common Ancestor of nodes A and B
getNodeDistance(A,B)
= pathLen(Root, A)
+ pathLen(Root, B)
- (2 * pathLen(Root, lca(A,B)))
public int getNodeDistance(TreeNode root, int n1, int n2) { }
C
Java
Python