Second Rightmost Node in a Binary Tree

Problem Statement

Given a binary tree, find the second rightmost node at the deepest level of the tree.

If the deepest level has only one node, decide (and clarify with the interviewer) whether to return the second rightmost from the level above, or return null.

Constraints

• 1 <= number of nodes <= 10^5
• Node values are unique
• Clarify the definition of "rightmost" before coding

Example

Input:

        1
       / \
      2   3
         / \
        4   5

Output: 4

Explanation: The deepest level is [4, 5]. The rightmost is 5, so the second rightmost is 4.

What the Interviewer Expects

1. Clarify the question first — "second rightmost" is ambiguous. Does it mean:

   • Second node from the right at the deepest level? (most common)
   • Second largest in some traversal order?

   Asking this shows maturity. The interviewer values clarification.

2. Level-order traversal (BFS) — process the tree level by level. Keep track of the last level's nodes.

3. At the end — the last processed level is the deepest. Return its second-to-last node.

4. Edge cases — deepest level has only 1 node, single-node tree, skewed tree.

5. Time: O(n), Space: O(width of tree).

Follow-ups

1. What if you need the second rightmost at EACH level, not just the deepest?
2. Can you solve it with DFS instead of BFS? How would you track depth?
3. What if "rightmost" means the rightmost node visible from the right side (right view)?
4. How would you find the Nth node from the right at the deepest level?