MEDIUM

DATA STRUCTURES AND ALGORITHMS

GRAPH THEORYSEARCHBINARY TREESTREES

Written By

Tom Wagner

Jared Skinner

The Right View of Binary Tree problem involves taking a binary tree as input and returning a list of the nodes that would be visible to an observer positioned directly to the right of the tree. The problem demands a firm grasp of tree traversal algorithms in order to arrive at a linear time complexity solution.

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.

**Constraints**

- The number of nodes in the tree is in the range
`[0, 100]`

`-100 <= Node.val <= 100`

input:

```
0
/ \
1 2
/ \ / \
3 4 5 6
```

```
1 0
2 / \
3 1 2
4 / \ / \
5 3 4 5 6
```

output: `[0, 2, 6]`

input:

```
0
/
1
/ \
3 4
```

```
1 0
2 /
3 1
4 / \
5 3 4
```

output: `[0, 1, 4]`

input:

```
0
/ \
1 2
/ /
3 5
```

```
1 0
2 / \
3 1 2
4 / /
5 3 5
```

output: `[0, 2, 5]`

Start AI Interview

We will present two different approaches to this problem. In the first approach, we will explore the nodes at each depth (distance from the root) and select the rightmost node. This type of algorithm is known as a **breadth-first traversal**. In the second approach, we will explore the tree from the right side to the left, drilling down as far as we can in each branch. This is known as a **depth-first traversal**.

For this first approach we will collect all nodes at each depth (we will refer to a collection of nodes at a given depth as a **layer**) . Once all nodes have been organized into layers we will select the rightmost node from each layer.

We will use a helper function that takes in a group of nodes and returns all child nodes. This will make collecting successive layers very easy!

```
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def get_children(nodes: list[Optional[TreeNode]]) -> list[Optional[TreeNode]]:
"""
Given a list of nodes, find all children nodes
"""
next_layer = []
for node in nodes:
if node.left != None:
next_layer.append(node.left)
if node.right != None:
next_layer.append(node.right)
return next_layer
def right_side_view(root: Optional[TreeNode]) -> List[int]:
if root == None:
return []
node_list = []
layers = []
next_layer = [root]
while next_layer != []:
layers.append(next_layer)
next_layer = get_children(next_layer)
for layer in layers:
node_list.append(layer[-1].val)
return node_list
```

```
1# Definition for a binary tree node.
2# class TreeNode:
3# def __init__(self, val=0, left=None, right=None):
4# self.val = val
5# self.left = left
6# self.right = right
7
8def get_children(nodes: list[Optional[TreeNode]]) -> list[Optional[TreeNode]]:
9 """
10 Given a list of nodes, find all children nodes
11 """
12 next_layer = []
13 for node in nodes:
14 if node.left != None:
15 next_layer.append(node.left)
16 if node.right != None:
17 next_layer.append(node.right)
18
19 return next_layer
20
21def right_side_view(root: Optional[TreeNode]) -> List[int]:
22 if root == None:
23 return []
24
25 node_list = []
26
27 layers = []
28 next_layer = [root]
29 while next_layer != []:
30 layers.append(next_layer)
31 next_layer = get_children(next_layer)
32
33 for layer in layers:
34 node_list.append(layer[-1].val)
35
36 return node_list
```

- Time complexity:
`O(n)`

where`n`

is the number of nodes. - Space complexity:
`O(n)`

where`n`

is the number of nodes.

**Note:** You might calculate the time/space complexity as `O(n+d)`

where `d`

is the depth of the tree since we need the additional `d`

time/space for our algorithm. However, this complexity boils down to `O(n)`

since `d <= n`

which implies `O(n+d) <= O(2n) = O(n)`

.

Our space complexity is a little bloated since we are storing an additional copy of our tree when building the layers. Additionally, while `d`

doesn't count against us in the complexities above, we can improve the real runtime of our solution. We are going to employ one of the most common tree-searching algorithms: **Depth First Search (DFS)**. This algorithm works by drilling down a single branch of the tree until it reaches the bottom and then it backtracks until it finds a new branch. Proceeding this way we can inspect each node exactly once.

The algorithm works as follows:

- Create a stack
`X`

where nodes to explore will be kept. - The root node is placed in
`X`

- While
`X`

has something in it, pop a node`N`

off`X`

, find all children of`N`

, and add them to`X`

.

**Note:** Another implementation of this algorithm is to use recursion in place of a stack.

**Note:** This algorithm can be used for more than just binary trees, but if you employ this strategy in a graph with loops you also have to keep track of which nodes you have visited so you don't end up looking at the same nodes repeatedly!

Now, we will employ this DFS algorithm and take the rightmost path first. While traversing we will also track how deep each node is. When inspecting a node, if we do not already have a node in our solution array at this depth, we will add this node. In this way, we will capture the right-most nodes of the tree.

```
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def right_side_view(root: Optional[TreeNode]) -> List[int]:
if root == None:
return []
node_list = []
stack = [(root, 0)]
while stack != []:
node, depth = stack.pop()
if node.left != None:
stack.append((node.left, depth+1))
if node.right != None:
stack.append((node.right, depth+1))
if depth >= len(node_list):
node_list.append(node.val)
return node_list
```

```
1# Definition for a binary tree node.
2# class TreeNode:
3# def __init__(self, val=0, left=None, right=None):
4# self.val = val
5# self.left = left
6# self.right = right
7
8def right_side_view(root: Optional[TreeNode]) -> List[int]:
9 if root == None:
10 return []
11
12 node_list = []
13 stack = [(root, 0)]
14 while stack != []:
15 node, depth = stack.pop()
16 if node.left != None:
17 stack.append((node.left, depth+1))
18 if node.right != None:
19 stack.append((node.right, depth+1))
20
21 if depth >= len(node_list):
22 node_list.append(node.val)
23
24 return node_list
```

- Time complexity:
`O(n)`

where`n`

is the number of nodes. We can't reduce this further since we need to check every node to know how deep the tree is. - Space complexity:
`O(d)`

where`d`

is the depth of the tree.

Watch Mock Interviews Featuring the Right View Of Binary Tree Question

interviewing.io is a mock interview platform, and people in our community routinely share their interview replays to help others get better. In the video below, you can watch people solve Right View of a Binary Tree. The interview is in C++. The interviewer is an anonymous senior engineer from FAANG.

FAANG InterviewC++ Interview

Advance this person to the next round?

Technical Skills:

4/4

Problem Solving Ability:

4/4

Communication Ability:

3/4

Show Transcript

interviewing.io is a **mock interview practice platform**. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

Interview prep and job hunting are chaos and pain. We can help. Really.