How Many Steps Separate Two Nodes
Implement distanceBetween
You are given the root of a binary tree with distinct node values, and two values a and b that both appear in the tree. Return the distance between the two nodes: the number of parent-child connections on the unique path that joins them. That path may go up from one node and then down to the other. If a and b are the same node the distance is 0.
You can treat the tree as an undirected graph and run a breadth-first search, or notice that the path always turns at the lowest shared ancestor, so the distance is the sum of the two depths measured from it.
Example 1:
Input: root = [15,8,22,4,11,19,30,2,6,9,13], a = 6, b = 13
Output: 4
Example 2:
Input: root = [15,8,22,4,11,19,30,2,6,9,13], a = 6, b = 4
Output: 1
Example 3:
Input: root = [15,8,22,4,11,19,30,2,6,9,13], a = 2, b = 30
Output: 5
+ 12 hidden test cases run on Submit.
Constraints:
- ●
2 ≤ number of nodes ≤ 100, and every node value is distinct, 1 ≤ node.val ≤ 1000 - ●
a and b are values that both exist in the tree (they may be equal) - ●
The tree is given as its root node; each node has a val, a left child and a right child - ●
The distance between two nodes is the number of parent-child connections (edges) on the unique path between them; that path may go up and then down. Return the distance between the a-node and the b-node (0 if they are the same node)
root =
a =
b =