Leftmost Deepest Tree Node

Given a binary tree root, find the value of the deepest node. If there’s more than one deepest node, then return the leftmost one.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Leftmost-Deepest-Tree-Node

Examples

Example 1

Input

• root =

Output

• answer = 4

Explanation

The nodes with values 4 and 2 are tied as deepest. Since 4 is more left, 4 should be returned.

Example 2

Input

• root =

Output

• answer = 2

Explanation

The node with value 2 is the deepest.

Solution