Last Node in a Complete Binary Tree

Asked in:
Flipkart

Problem Description

You are given the root of a complete binary tree A.
You have to return the value of the rightmost node in the last level of the binary tree.

Try to find a solution with a better time complexity than O(N).

Problem Constraints

1 <= Number of nodes in the binary tree <= 10⁵

Input Format

The first argument is the root of a binary tree A.

Output Format

Return a single integer denoting the value of the rightmost node in the last level of the binary tree.

Example Input

Input 1:

Input 2:

Example Output

Output 1:

Output 2:

Example Explanation

Explanation 1:

There is only a single node in the last level of the binary tree.
Therefore, the answer is 2.

Explanation 2:

There a two nodes in the last level of the tree.
The rightmost nodes is 3.

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.

Start solving Last Node in a Complete Binary Tree on Interview Code Editor

Hints

Hint 1
Solution Approach
Complete Solution

Asked In:

Flipkart

Last Node in a Complete Binary Tree

Discussion