Breadth-First Search
Rightmost Node
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Given the root of a binary tree, return the rightmost node at each level of the tree. The output should be a list containing only the values of those nodes.
Example 1:
Input:
[1, 3, 4, null, 2, 7, null, 8]
Output: [1, 4, 7, 8]
Example 2:
Input:
[1,2,5,3,null,null,null,null,4]
Output: [1, 5, 3, 4]
Explanation
Since the question is asking for the rightmost node at each level, we should recognize that a level-order breadth-first traversal of the binary tree is the most straightforward way to solve this problem.
We can start by initialize an empty list to store the rightmost nodes. Recall that in a level-order traversal, we first find the number of nodes at the current level, and then we use a for-loop to loop over all the nodes at that level. When the count of the for loop is equal to the number of nodes at the current level minus one, we know that the current node is the rightmost node at that level, so we can add it to our list.
Solution
Python
class Solution:def rightmostNode(self, root: TreeNode) -> List[int]:if not root:return []nodes = []queue = deque([root])while queue:level_size = len(queue)for i in range(level_size):node = queue.popleft()# current node is the rightmost nodeif i == level_size - 1:nodes.append(node.val)# add nodes as normal to the queueif node.left:queue.append(node.left)if node.right:queue.append(node.right)return nodes
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(N) where N is the number of nodes in the tree. We visit each node exactly once, and each node, we perform a constant amount of work.
Space Complexity: O(N) In the worst case, each node in the tree is on its own level, so the output list will contain N elements.
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.