Hops Between Two Keys

Medium

You are given the root of a binary tree whose node values are all distinct, and two values first and second, both present in the tree. Return the distance between the nodes holding these values: the number of edges on the path from one to the other. Edges can be walked in both directions, up and down. If first equals second, the distance is 0.

Example 1

root=tree_node([10, 4, 15, 2, 7, None, 20]), first=7, second=20 → 4

The path 7 → 4 → 10 → 15 → 20 uses four edges.

Example 2

root=tree_node([10, 4, 15, 2, 7, None, 20]), first=4, second=2 → 1

2 is a child of 4, so they are one edge apart.

Example 3

root=tree_node([8, 3]), first=3, second=3 → 0

A node is 0 edges away from itself.

Constraints

1 ≤ number of nodes ≤ 10⁴
0 ≤ Node.val ≤ 10⁹, all values are distinct
first and second are present in the tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Hash Table Binary Tree

Similar problems

Tree Columns, Top Down Medium Smallest Cover of the Bottom Row Medium Where the Deepest Leaves Meet Medium Spread Through the Tree Medium Replace With Cousin Sums Medium

Input

root=tree_node([10, 4, 15, 2, 7, None, 20]), first=7, second=20

Expected

Run checks the first 3 tests in your browser. Submit checks all 33 tests on the server, hidden ones included.