Sibling Tree Value

You are given an integer k and a binary search tree root, where each node is either a leaf or contains 2 children.

Find the node containing the value k, and return its sibling’s value.

You can assume that the solution always exists (e.x. root won’t have value of k)

Constraints

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

https://binarysearch.com/problems/Sibling-Tree-Value

Examples

Example 1

Input

• root =

• k = 1

Output

• answer = 3

Example 2

Input

• root =

• k = 1

Output

• answer = 8

Example 3

Input

• root =

• k = 9

Output

• answer = 6

Solution