Solution: Problem Challenge 2: Right View of a Binary Tree

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Problem Challenge 2: Right View of a Binary Tree

Table of Contents

Contents are not accessible

Problem Statement

Given a root of the binary tree, return an array containing nodes in its right view.

The right view of a binary tree consists of nodes that are visible when the tree is viewed from the right side. For each level of the tree, the last node encountered in that level will be included in the right view.

Examples

Example 1

Input: root = [1, 2, 3, 4, 5, 6, 7]

Expected Output: [1, 3, 7]
Justification:
- The last node at level 0 is 1.
- The last node at level 1 is 3.
- The last node at level 2 is 7.

Example 2

Input: root = [12, 7, 1, null, 9, 10, 5, null, 3]

Expected Output: [12, 1, 5, 3]
Justification:
- The last node at level 0 is 12.
- The last node at level 1 is 1.
- The last node at level 2 is 5.
- The last node at level 3 is 3.

Example 3

Input: root = [8, 4, 9, 3, null, null, 10, 2]

Expected Output: [8, 9, 10, 2]
Justification:
- The last node at level 0 is 8.
- The last node at level 1 is 9.
- The last node at level 2 is 10.
- The last node at level 3 is 2.

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Solution

To solve this problem, we will use the Breadth-First Search (BFS) agorithm to traverse the binary tree and compute the right view of the tree. It processes the tree level by level, ensuring that at each level, the last node encountered (rightmost node) is stored in the result list. A queue is used to facilitate level-wise traversal, and at the end of each level, the last node is added to the result.

Step-by-Step Algorithm

Base Case: If the root is null, return an empty list since there are no nodes to process.
Initialize Queue: Create an empty queue and add the root node to it. This queue is used to traverse the tree level by level, starting from the root.
While the Queue is Not Empty:
- Determine Level Size: Calculate the number of nodes at the current level using queue.size(). This ensures that we process all nodes at the same level before moving to the next level.
- Process Each Node at the Current Level:
  - For each node in the current level:
    - Dequeue the Current Node: Poll the node from the front of the queue.
    - Add its Left Child to the Queue: If the current node has a left child, add it to the queue to process in the next level.
    - Add its Right Child to the Queue: If the current node has a right child, add it to the queue for the next level.
- Add the Last Node of the Level to the Result: After processing all nodes at the current level, add the value of the last node (rightmost node) to the result list. This node will represent the right view at that level.
Repeat: Continue this process for each level until the queue is empty, meaning all levels have been processed.
Return the Result: After processing all levels, the result list will contain the nodes visible from the right view of the tree.

Algorithm Walkthrough

Input: root = [12, 7, 1, null, 9, 10, 5, null, 3]

Step-by-Step Execution

Initialization:
- The root node is 12. Add 12 to the queue.
Queue: [12] Result: []
Level 1:
- queue.size() is 1, meaning there is 1 node at this level.
- Dequeue node 12.
- Add its left child (7) and right child (1) to the queue.
- Add 12 in the result list.
Queue: [7, 1] Result: [12]
Level 2:
- queue.size() is 2, meaning there are 2 nodes at this level.
- Dequeue node 7. Add its right child (9) to the queue (it has no left child).
- Dequeue node 1. Add its left child (10) and right child (5) to the queue.
- Since 1 is the last node at this level, add it to the result.
Queue: [9, 10, 5] Result: [12, 1]
Level 3:
- queue.size() is 3, meaning there are 3 nodes at this level.
- Dequeue node 9. Add its right child (3) to the queue (it has no left child).
- Dequeue node 10. It has no children.
- Dequeue node 5. It has no children.
- Since 5 is the last node at this level, add it to the result.
Queue: [3] Result: [12, 1, 5]
Level 4:
- queue.size() is 1, meaning there is 1 node at this level.
- Dequeue node 3. Since it's the only node at this level, add it to the result.
- Node 3 has no children, so nothing is added to the queue.
Queue: [] Result: [12, 1, 5, 3]
Completion: The queue is now empty, meaning all levels of the tree have been processed. The right view of the tree is complete.

Final Output: [12, 1, 5, 3]

Code

Here is the code for this algorithm:

Python3

. . . .

Time Complexity

The time complexity of the above algorithm is $O(N)$ , where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity

The space complexity of the above algorithm will be $O(N)$ for the queue. Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level), therefore we will need $O(N)$ space to store them in the queue.
Also, we use space $O(N)$ space for result list. For the skewed tree we need to store all N elements in the result list.