Hops Between Two Stored Values

In a binary search tree with distinct values, a message travels along edges from the node holding a to the node holding b. Return the number of edges on that route. Both values are present; the route from a node to itself has length 0. Use the ordering rule; you do not need to explore the whole tree.

Examples

         12
        /  \
       7    18
      / \   / \
     3   9 15  22
      \
       5

Input:  root = build_tree([12, 7, 18, 3, 9, 15, 22, None, 5]), a = 5, b = 9
Output: 3        (5 - 3 - 7 - 9)

Input:  root = build_tree([12, 7, 18, 3, 9, 15, 22, None, 5]), a = 12, b = 22
Output: 2

Constraints

• 1 <= number of nodes <= 3000
• Values are distinct; a and b are both in the tree
• O(h) time

Goals

• Locate the split node of two search paths
• Add the two depths below the split node