_1602. Find Nearest Right Node in Binary Tree.md

1602. Find Nearest Right Node in Binary Tree

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 03, 2024

Last updated : July 03, 2024

---

Related Topics : Tree, Breadth-First Search, Binary Tree

Acceptance Rate : 75.22 %

---

Solutions

• m1602 v1 Queue.java
• m1602 v1 Queue.py

Java

m1602 v1 Queue.java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode findNearestRightNode(TreeNode root, TreeNode u) {
        Queue<Integer> depths = new LinkedList<>();
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        depths.add(1);

        while (!depths.isEmpty()) {
            TreeNode curr = nodes.remove();
            int depth = depths.remove();

            if (curr == u) {
                if (depths.isEmpty()) {
                    return null;
                }
                if (depths.remove() == depth) {
                    return nodes.remove();
                }
                return null;
            }

            if (curr.left != null) {
                nodes.add(curr.left);
                depths.add(depth + 1);
            }
            if (curr.right != null) {
                nodes.add(curr.right);
                depths.add(depth + 1);
            }
        }
        return null;
    }
}

Python

m1602 v1 Queue.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findNearestRightNode(self, root: TreeNode, u: TreeNode) -> Optional[TreeNode]:
        toVisit = deque()
        toVisit.append((root, 1))

        while toVisit :
            curr, depth = toVisit.popleft()

            if curr == u :
                if not toVisit :
                    return None
                nxt, depthNxt = toVisit.popleft()
                if depthNxt == depth :
                    return nxt
            
            if curr.left :
                toVisit.append((curr.left, depth + 1))
            if curr.right :
                toVisit.append((curr.right, depth + 1))

        return None