Algo

Binary Tree Right Side View (Leetcode #199)

Nawat Sunthornyanakit's photo
Nawat Sunthornyanakit
·

3 min read

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 100].

  • -100 <= Node.val <= 100

Answer

The problem asks us to find the rightmost node at each level of the tree when viewed from the right side. This can be achieved using Breadth-First Search (BFS), which traverses the tree level by level. At each level, we collect the rightmost node.

Approach:

  1. Initialize an empty list res to store the rightmost nodes.

  2. Use a queue (q) to help with level-order traversal. Start by adding the root node to the queue.

  3. For each level:

    • Initialize a temporary list temp to hold the nodes at the current level.

    • Process each node in the queue, adding its value to temp.

    • Add the left and right children of each node to the queue (if they exist).

    • After processing all nodes at the current level, add the last element in temp to res (this represents the rightmost node).

  4. Continue until the queue is empty, indicating that all levels have been processed.

  5. Return res as the final output.

Python Code:

pythonCopy code# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        q = collections.deque()
        q.append(root)
        while q:
            temp = []
            for i in range(len(q)):
                node = q.popleft() 
                if node:
                    temp.append(node.val)
                    q.append(node.left)
                    q.append(node.right)
            if temp:
                res.append(temp[-1])
        return res

Summary:

  • We traverse each level of the tree, collecting nodes in a list (temp).

  • The left and right children of each node are added to the queue for the next level.

  • After completing each level, we take the rightmost node from temp and store it in our final output list (res).

  • The loop continues until the queue is empty, indicating that we have reached the last level.

Time Complexity:

The time complexity of this code is O(N), where N is the number of nodes in the tree, as we visit each node once.

Space Complexity:

The space complexity is O(W), where W is the maximum width of the tree. This is because we store all nodes at the current level in the queue. In some cases, the height of the tree might be greater than the maximum width, leading to a space complexity of O(H), where H is the height of the tree.

leetcodePython