199. Binary Tree Right Side View

MediumTreeDepth-First SearchBreadth-First SearchBinary Tree
Leetcode Link

Problem Description

This problem asks us to determine the values of the nodes visible when we look at a binary tree from the right side. This essentially means that we want the last node's value in each level of the tree, proceeding from top to bottom.

A binary tree is a data structure where each node has at most two children referred to as the left child and the right child.

Intuition

To solve this problem, we can use a level-order traversal strategy. The level-order traversal involves traveling through the tree one level at a time, starting at the root. This is typically done using a queue data structure where we enqueue all nodes at the current level before we proceed to the next level.

While performing a level-order traversal, we can keep track of the nodes at the current level by counting how many nodes are in the queue before we start processing the level. Then, as we enqueue their children, we can observe the rightmost node's value of each level (which will be the last one we encounter in the queue for that level) and record that value.

This approach allows us to see the tree as if we were standing on its right side and collect the values of the nodes that would be visible from that perspective.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Solution Approach

The solution uses a level-order traversal approach, utilizing a queue to track the nodes at each level. Here's a step-by-step walkthrough of the implementation:

  1. We initialize an empty list ans which will store the values of the rightmost nodes at each level of the binary tree.

  2. We check if the root is None (i.e., the tree is empty) and if so, return the empty list ans. There's nothing to traverse if the tree is empty.

  3. A queue q is initialized with the root node as its only element. This queue will help in the level-order traversal, keeping track of nodes that need to be processed.

  4. We begin a while loop which continues as long as there are nodes in the queue q. Each iteration of this loop represents traversing one level of the binary tree.

  5. At the beginning of each level traversal, we append the value of the last node in the queue (the rightmost node of the current level) to the ans list. We use q[-1].val to fetch this value as we are using a double-ended queue deque from Python's collections module.

  6. We then enter another loop to process all nodes at the current level, which are already in the queue. We find the number of nodes in the current level by the current length of the queue len(q).

  7. Inside this inner loop, we pop the leftmost node from the queue using q.popleft() and check if this node has a left child. If it does, we append the left child to the queue.

  8. We also check if the node has a right child, and if so, we append the right child to the queue.

  9. After this inner loop finishes, all the nodes of the next level have been added to the queue, and we proceed to the next iteration of the while loop to process the next level.

  10. When there are no more nodes in the queue, it indicates that we have completed traversing the binary tree. At this point, the while loop exits.

  11. Finally, we return the ans list, which now contains the values of the rightmost nodes of each level, as seen from the right-hand side of the tree.

Through this algorithm, we effectively conduct a breadth-first search (BFS) while taking a snapshot of the last node at each level, resulting in the view from the right side of the binary tree.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Example Walkthrough

Let's take a small example to illustrate the solution approach. Consider the following binary tree:

1    1
2   / \
3  2   3
4     / \
5    5   4

Now, let us walk through the solution using the presented level-order traversal approach.

  1. Start by initializing the answer list ans = [] which will hold the values of the rightmost nodes.

  2. Since the root is not None, we don't return an empty list but proceed with the next steps.

  3. Initialize the queue q with the root node of the binary tree, which in our case is the node with the value 1. So, q = deque([1]).

  4. Enter the while loop, as our queue has one element at this point.

  5. Queue state: [1]. The rightmost node is the last element of the queue, which is 1. Append 1 to ans, so ans = [1].

  6. The number of nodes at the current level (root level) is 1. We proceed to process this level.

  7. Pop 1 from the queue using q.popleft(). Node 1 has two children: 2 (left child) and 3 (right child). Enqueue these children into q, resulting in q = deque([2, 3]).

  8. Now, the queue has the next level of nodes, so we loop back to the outer while loop.

  9. Queue state: [2, 3]. The rightmost node now is 3. We add value 3 to ans, so ans = [1, 3].

  10. There are two nodes at this level. We begin the inner loop to process both.

  11. Pop 2 from the queue using q.popleft(). Node 2 has no children, so we do not add anything to the queue.

  12. Pop 3 from the queue. It has two children: 5 (left child) and 4 (right child). Enqueue these children, making q = deque([5, 4]).

  13. All nodes of the current level are processed, loop back to the outer loop.

  14. Queue state: [5, 4]. The rightmost node is 4. Append 4 to ans, so ans = [1, 3, 4].

  15. This level has two nodes. We enter the inner loop to process both nodes.

  16. Pop 5 from the queue. 5 has no children, so we move on.

  17. Pop 4 from the queue. 4 has no children as well.

  18. The queue is empty, so the outer while loop exits.

  19. We have traversed the entire tree and recorded the rightmost node at each level.

  20. The final answer list ans now contains [1, 3, 4], which are the values of the nodes visible from the right-hand side of the binary tree.

Through the level-order traversal, we select the last node's value at each level, aligning with the view one would see if they looked at the tree from its right side.

Solution Implementation

1# Import the deque class from collections for queue implementation
2from collections import deque
3
4# Definition for a binary tree node.
5class TreeNode:
6    def __init__(self, val=0, left=None, right=None):
7        self.val = val
8        self.left = left
9        self.right = right
10
11class Solution:
12    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
13        # Initialize the array to hold the right side view elements
14        right_side_view = []
15      
16        # If the tree is empty, return the empty list
17        if root is None:
18            return right_side_view
19      
20        # Use deque as a queue to hold the nodes at each level
21        queue = deque([root])
22      
23        # Continue until the queue is empty
24        while queue:
25            # The rightmost element at the current level is visible from the right side
26            right_side_view.append(queue[-1].val)
27          
28            # Iterate over nodes at the current level
29            for _ in range(len(queue)):
30                # Pop the node from the left side of the queue
31                current_node = queue.popleft()
32              
33                # If left child exists, add it to the queue
34                if current_node.left:
35                    queue.append(current_node.left)
36              
37                # If right child exists, add it to the queue
38                if current_node.right:
39                    queue.append(current_node.right)
40                  
41        # Return the list containing the right side view of the tree
42        return right_side_view
43
1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.Deque;
4import java.util.List;
5
6// Definition for a binary tree node.
7class TreeNode {
8    int val;
9    TreeNode left;
10    TreeNode right;
11
12    TreeNode() {}
13  
14    TreeNode(int val) { 
15        this.val = val; 
16    }
17  
18    // Constructor to initialize binary tree nodes with values and its children reference
19    TreeNode(int val, TreeNode left, TreeNode right) {
20        this.val = val;
21        this.left = left;
22        this.right = right;
23    }
24}
25
26class Solution {
27  
28    // Function to get a list of integers representing the right side view of the binary tree
29    public List<Integer> rightSideView(TreeNode root) {
30        // Initialize an answer list to store the right side view
31        List<Integer> answer = new ArrayList<>();
32      
33        // Return empty list if the root is null
34        if (root == null) {
35            return answer;
36        }
37      
38        // Initialize a dequeue to perform level order traversal
39        Deque<TreeNode> queue = new ArrayDeque<>();
40      
41        // Add the root to the queue as the start of traversal
42        queue.offer(root);
43      
44        // Perform a level order traversal to capture the rightmost element at each level
45        while (!queue.isEmpty()) {
46            // Get the rightmost element of the current level and add to the answer list
47            answer.add(queue.peekLast().val);
48          
49            // Iterate through nodes at current level
50            for (int n = queue.size(); n > 0; --n) {
51                // Poll the node from the front of the queue
52                TreeNode node = queue.poll();
53              
54                // If left child exists, add it to the queue
55                if (node.left != null) {
56                    queue.offer(node.left);
57                }
58              
59                // If right child exists, add it to the queue
60                if (node.right != null) {
61                    queue.offer(node.right);
62                }
63            }
64        }
65      
66        // Return the list containing the right side view of the tree
67        return answer;
68    }
69}
70
1#include <vector>
2#include <queue>
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode() : val(0), left(nullptr), right(nullptr) {}
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    // Function to get the right side view of a binary tree.
17    vector<int> rightSideView(TreeNode* root) {
18        vector<int> rightView; // Stores the right side view elements
19        if (!root) {
20            return rightView; // If the root is null, return an empty vector
21        }
22
23        queue<TreeNode*> nodesQueue; // Queue to perform level order traversal
24        nodesQueue.push(root);
25
26        while (!nodesQueue.empty()) {
27            // Add the rightmost element of current level to the right view
28            rightView.emplace_back(nodesQueue.back()->val);
29
30            // Traverse the current level
31            for (int levelSize = nodesQueue.size(); levelSize > 0; --levelSize) {
32                TreeNode* currentNode = nodesQueue.front();
33                nodesQueue.pop();
34
35                // If left child exists, add it to the queue for next level
36                if (currentNode->left) {
37                    nodesQueue.push(currentNode->left);
38                }
39
40                // If right child exists, add it to the queue for next level
41                if (currentNode->right) {
42                    nodesQueue.push(currentNode->right);
43                }
44            }
45        }
46
47        return rightView; // Return the final right side view of the binary tree
48    }
49};
50
1// Definition for a binary tree node.
2class TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
7    this.val = val === undefined ? 0 : val;
8    this.left = left === undefined ? null : left;
9    this.right = right === undefined ? null : right;
10  }
11}
12
13/**
14 * Gets the values of the rightmost nodes at every level of the binary tree.
15 * @param root - The root of the binary tree.
16 * @returns An array of numbers representing the rightmost values for each level.
17 */
18function rightSideView(root: TreeNode | null): number[] {
19  // Initialize an array to hold the answer.
20  const rightMostValues = [];
21
22  // If the root is null, return the empty array.
23  if (!root) {
24    return rightMostValues;
25  }
26
27  // Initialize a queue and enqueue the root node.
28  const queue: TreeNode[] = [root];
29
30  // Iterate as long as there are nodes in the queue.
31  while (queue.length) {
32    const levelSize = queue.length;
33  
34    // Get the last element of the queue (rightmost of this level)
35    rightMostValues.push(queue[levelSize - 1].val);
36  
37    // Traverse the nodes of the current level.
38    for (let i = 0; i < levelSize; i++) {
39      // Remove the first element from the queue.
40      const node = queue.shift();
41    
42      // If the node has a left child, add it to the queue.
43      if (node.left) {
44        queue.push(node.left);
45      }
46    
47      // If the node has a right child, add it to the queue.
48      if (node.right) {
49        queue.push(node.right);
50      }
51    }
52  }
53
54  // Return the array of rightmost values.
55  return rightMostValues;
56}
57
Not Sure What to Study? Take the 2-min Quiz๏ผš

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Time and Space Complexity

Time Complexity

The given Python function rightSideView() performs a level-order traversal on a binary tree using a queue. In the worst case, it will visit all nodes of the tree once. Therefore, if there are N nodes in the tree, the time complexity is:

O(N)

Space Complexity

The space complexity is determined by the maximum number of nodes that can be held in the queue at any given time, which would be the maximum width of the tree. This width corresponds to the maximum number of nodes on any level of the tree. In the worst case for a completely balanced binary tree, this would be N/2 (for the last level). Therefore, the space complexity is:

O(N)

In a less balanced scenario, the space complexity will fluctuate, but it cannot exceed the total number of nodes in the tree, hence still O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ