[Top Interview 150] 199. Binary Tree Right Side View

Solution)

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # Base Case
        if not root: return None

        # queue will store nodes in each level
        # res will save values of nodes on the right side of tree
        queue, res = deque(), []
        queue.append(root)

        while queue:
            # Append the value of nodes on the right side to res
            res.append(queue[0].val)

            for i in range(len(queue)):
                # Pop nodes from the left of queue
                # This pops the rightmost node in tree
                cur = queue.popleft()

                # Append children from right to left
                if cur.right:
                    queue.append(cur.right)
                if cur.left:
                    queue.append(cur.left)

        return res

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(n)
Note: n = number of nodes
 

Explanation)

We'll use BFS method to find nodes from right to left in each level.
 
Then we'll return the values of the rightmost nodes and remove other leftover nodes after appending their children to our array.
 
The main idea is that
1) we'll append nodes from right to left to our array
2) save the values of the rightmost nodes in other array
3) remove the other useless leftover nodes after appending their children to our array
 

1. Base Case & Initialization)

If the tree is empty, there is no rightmost node so return None.
 
If the tree is not empty, we'll initialize our arrays.
queue is a deque that will save nodes from right to left in each level. 
res is a list that will save values of all the rightmost nodes.
 

def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # 1. Base Case & Initialization
        if not root: return None

        queue, res = deque(), []
        queue.append(root)

 

2. Append the value of rightmost node)

We'll iterate the tree while queue is not empty.
 
While iterating, we'll first append value of the rightmost node in each level.
Because we'll save nodes from right to left, the rightmost node will always be on the 0th position.
 

def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # 1. Base Case & Initialization
        if not root: return None

        queue, res = deque(), []
        queue.append(root)

        while queue:
            # 2. Append the value of rightmost node
            res.append(queue[0].val)

 

3. Pop all the nodes and add their children to queue)

Now that we saved the value of the rightmost node, it's time to remove unnecessary nodes.
 
Currently, queue has all the nodes (which are now useless) in the current level.
So, we'll pop all the nodes in the current level and append their children to queue.
 
The appending order is important.
 
Since we want our rightmost node to be always on the 0th position of queue, we need to popleft. 
The reason we popleft is to always save the nodes from right to left in each level.
 
 
After all the iteration, we'll have all the righmost nodes' values in res.
 

def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # 1. Base Case & Initialization

        while queue:
            # 2. Append the value of rightmost node
            res.append(queue[0].val)

            # 3. Pop all the nodes and add their children to queue
            for i in range(len(queue)):
                cur = queue.popleft()

                if cur.right:
                    queue.append(cur.right)
                if cur.left:
                    queue.append(cur.left)

        return res

---

 
 
I wanted to use only one space instead of having additional space res, but it got too complicated. If you know how to do it, please let me know!