Next Node on Its Right

You are given a binary tree root containing unique values, and an integer target. Find the node with value target and return the node that’s directly right of it on its level. If the target node doesn’t exist or if it’s already in the rightmost position, return null.

Constraints

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

https://binarysearch.com/problems/Next-Node-on-Its-Right

Examples

Example 1

Input

• tree =

• target = 5

Output

• answer =

Example 2

Input

• tree =

• target = 3

Output

• answer =

Explanation

There’s no node directly to the right of 3.

Example 3

Input

• tree =

• target = 2

Output

• answer =

Explanation

Node 2 doesn’t exist.

Solution