1602. Find Nearest Right Node in Binary Tree
leetcode.com/problems/find-nearest-right-node-in-binary-tree/
Given the root of a binary tree and a node u in the tree, return the nearest node on the same level that is to the right of u, or return null if u is the rightmost node in its level.
Example 1:
Input: root = [1,2,3,null,4,5,6], u = 4 Output: 5 Explanation: The nearest node on the same level to the right of node 4 is node 5.
Example 2:
Input: root = [3,null,4,2], u = 2 Output: null Explanation: There are no nodes to the right of 2.
Example 3:
Input: root = [1], u = 1 Output: null
Example 4:
Input: root = [3,4,2,null,null,null,1], u = 4 Output: 2
Constraints:
- The number of nodes in the tree is in the range [1, 105].
- 1 <= Node.val <= 105
- All values in the tree are distinct.
- u is a node in the binary tree rooted at root.
Solution
Overview
DFS vs. BFS
There are two ways to traverse the tree: DFS depth first search and BFS breadth first search. Here is a small summary
BFS traverses level by level, and DFS first goes to the leaves.
Which approach to choose, BFS or DFS?
-
The problem is to return the nearest node on the same level that is to the right of u, so it's the way more natural to implement BFS here.
-
Time complexity is the same \mathcal{O}(N) both for DFS and BFS since one has to visit all nodes.
-
Space complexity is \mathcal{O}(H) for DFS and
\mathcal{O}(D) for BFS, where H is a tree height, and D is a tree diameter. They both result in \mathcal{O}(N) space in the worst-case scenarios: skewed tree for DFS and complete tree for BFS.
Let's use the opportunity to check out three different BFS implementations with the queue, Approach 1 - Approach 3.
If you prefer to use DFS on the interviews - check the Approach 4.
BFS implementation
All three implementations use the queue in a standard BFS way:
-
Push the root into the queue.
-
Pop-out a node from the left.
-
Push the left child into the queue, and then push the right child.
Three BFS approaches
The difference is how to identify the end of the level:
-
Two queues, one for the previous level and one for the current.
-
One queue with sentinel to mark the end of the level.
-
One queue + level size measurement.
Approach 1: BFS: Two Queues
Let's use two queues: one for the current level, and one for the next. The idea is to pop the nodes one by one from the current level and push their children into the next level queue.
Algorithm
-
Initiate two queues: one for the current level, and one for the next. Add root into nextLevel queue.
-
While nextLevel queue is not empty:
-
Initiate the current level: currLevel = nextLevel, and empty the next level nextLevel.
-
While current level queue is not empty:
-
Pop out a node from the current level queue.
-
If this node is u, return the next node from the queue. If there is no more nodes in nextLevel queue, return null.
-
Add first left and then right child node into nextLevel queue.
-
-
Implementation
Complexity Analysis
-
Time complexity: \mathcal{O}(N) since one has to visit each node.
-
Space complexity: \mathcal{O}(D) to keep the queues, where D is a tree diameter. Let's use the last level to estimate the queue size. This level could contain up to N/2 tree nodes in the case of complete binary tree.
Approach 2: BFS: One Queue + Sentinel
Another approach is to push all the nodes in one queue and to use a sentinel node to separate the levels. Typically, one could use null as a sentinel.
The first step is to initiate the first level: root + null as a sentinel. Once it's done, continue to pop the nodes one by one from the left and push their children to the right. Stop each time the current node is null because it means we hit the end of the current level. Each stop is a time to push null in the queue to mark the end of the next level.
Algorithm
-
Initiate the queue by adding a root. Add null sentinel to mark the end of the first level.
-
Initiate the current node as root.
-
While queue is not empty:
-
Pop the current node from the queue curr = queue.poll().
-
If this node is u, return the next node from the queue. If there is no more nodes in the queue, return null.
-
If the current node is not null:
-
Add first left and then right child node into the queue.
-
Update the current node: curr = queue.poll().
-
-
Now, the current node is null, i.e. we reached the end of the current level. If the queue is not empty, push the null node as a sentinel, to mark the end of the next level.
-
Implementation
Note that ArrayDeque in Java doesn't support null elements, and hence the data structure to use here is LinkedList.
Complexity Analysis
-
Time complexity: \mathcal{O}(N) since one has to visit each node.
-
Space complexity: \mathcal{O}(D) to keep the queues, where D is a tree diameter. Let's use the last level to estimate the queue size. This level could contain up to N/2 tree nodes in the case of complete binary tree.
Approach 3: BFS: One Queue + Level Size Measurements
Instead of using the sentinel, we could write down the length of the current level.
Algorithm
-
Initiate the queue by adding a root.
-
While the queue is not empty:
-
Write down the length of the current level: levelLength = queue.size().
-
Iterate over i from 0 to level_length - 1:
-
Pop the current node from the queue: node = queue.poll().
-
If this node is u, return the next node from the queue. Check that the next node is on the same level: i != levelLength - 1, otherwise return null.
-
Add first left and then right child node into the queue.
-
-
Implementation
Complexity Analysis
-
Time complexity: \mathcal{O}(N) since one has to visit each node.
-
Space complexity: \mathcal{O}(D) to keep the queues, where D is a tree diameter. Let's use the last level to estimate the queue size. This level could contain up to N/2 tree nodes in the case of complete binary tree.
Approach 4: Recursive DFS: Preorder Traversal
Everyone likes recursive DFS because of its simplicity, so let's add it here as well. The idea is straightforward: to perform standard preorder traversal of the tree, starting each time from the leftmost child.
Implementation
Complexity Analysis
-
Time complexity: \mathcal{O}(N) since one has to visit each node.
-
Space complexity: \mathcal{O}(H) to keep the recursion stack, where H is a tree height. The worst-case situation is a skewed tree when H = N.
그냥 내코드만 첨부함..
class Solution:
def findNearestRightNode(self, root: TreeNode, u: TreeNode) -> TreeNode:
if not root:
return null
que = []
que.append(root)
found = False
while que:
level_size = len(que)
while level_size > 0:
node = que.pop(0)
if found:
return node
if node == u:
found = True
if node.left: que.append(node.left)
if node.right: que.append(node.right)
level_size -= 1
found = False
return False
