Second Place

Given a binary tree root, return the depth of the second deepest leaf. Note that if there are multiple deepest leaves, the second deepest leaf is the next highest one.

The root has a depth of 0 and you can assume the answer is guaranteed to exist for the trees given.

Constraints

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

https://binarysearch.com/problems/Second-Place

Examples

Example 1

Input

• root =

Output

• answer = 1

Explanation

The the second deepest leaf is 2 which exists at depth 1

Solution