Spread Through the Tree

Medium

You are given the root of a binary tree whose node values are all distinct, and an integer origin. At minute 0 the node with value origin hears a piece of news. Every minute after that, each node that knows the news passes it to its neighbours: its parent and its children. Return the number of minutes until every node in the tree knows the news.

Example 1

root=tree_node([7, 2, 9, 4, None, None, 8, 1]), origin=9 → 4

Minute 0: 9. Minute 1: 7 and 8. Minute 2: 2. Minute 3: 4. Minute 4: 1. The answer is 4.

Example 2

root=tree_node([3, 5, 6]), origin=3 → 1

Both children of the root get the signal in one minute.

Example 3

root=tree_node([12]), origin=12 → 0

There is a single node and it already has the news, so 0 minutes.

Constraints

1 ≤ number of nodes ≤ 10⁵
1 ≤ Node.val ≤ 10⁵
All values are distinct
A node with value origin exists 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 Hops Between Two Keys Medium Replace With Cousin Sums Medium

Input

root=tree_node([7, 2, 9, 4, None, None, 8, 1]), origin=9

Expected

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