Teaching Kids Programming – Left/Right Side View of a Binary Tree using Depth/Breadth First Search Algorithms

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Given the following Binary Tree, the left side view will be [6, 3, 6] while the right side view is [6, 2, 4].

We can use either Depth First Search or Breadth First Search Algorithm to Traverse the binary tree.

Left/Right Side View of a Binary Tree using Breadth First Search Algorithms

We use the queue (aka deque in Python) to implement the BFS (Breadth First Search Algorithm). We deque (pop) all elements in current queue at once and push their kids back to the queue, thus we know at any time, the nodes in the queue belong to the same level.

We take the rightmost (right side view) aka q[-1] and push to the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        q = deque([root])
        ans = []
        while q:
            n = len(q)
            ans.append(q[-1].val)
            for i in range(n):
                x = q.popleft()
                if x.left:
                    q.append(x.left)
                if x.right:
                    q.append(x.right)
        return ans
# 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
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        q = deque([root])
        ans = []
        while q:
            n = len(q)
            ans.append(q[-1].val)
            for i in range(n):
                x = q.popleft()
                if x.left:
                    q.append(x.left)
                if x.right:
                    q.append(x.right)
        return ans

Or leftmost aka q[0] if we want to take the left side view:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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
class Solution:
    def leftSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        q = deque([root])
        ans = []
        while q:
            n = len(q)
            ans.append(q[0].val)
            for i in range(n):
                x = q.popleft()
                if x.left:
                    q.append(x.left)
                if x.right:
                    q.append(x.right)
        return ans
# 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
class Solution:
    def leftSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        q = deque([root])
        ans = []
        while q:
            n = len(q)
            ans.append(q[0].val)
            for i in range(n):
                x = q.popleft()
                if x.left:
                    q.append(x.left)
                if x.right:
                    q.append(x.right)
        return ans

Left/Right Side View of a Binary Tree using Depth First Search Algorithms

We may use Recursion to implement the Depth First Search. For level side view, we can do Inorder traversal and store the right side view using a hash map aka dictionary. Since we visit right trees last, so the values ​​last updated will the rightmost nodes for each level.

For the Depth First Search, we need to pass down the levels which are the keys to the hash map.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        ans = []
        data = defaultdict(int)
        def dfs(root, lvl):
            if not root:
                return
            dfs(root.left, lvl + 1)
            data[lvl] = root.val
            dfs(root.right, lvl + 1)
        dfs(root, 0)
        for i in sorted(data.keys()):
            ans.append(data[i])
        return ans
# 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
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        ans = []
        data = defaultdict(int)
        def dfs(root, lvl):
            if not root:
                return
            dfs(root.left, lvl + 1)
            data[lvl] = root.val
            dfs(root.right, lvl + 1)
        dfs(root, 0)
        for i in sorted(data.keys()):
            ans.append(data[i])
        return ans

We can simply swap the traversal of left and right trees eg Reverse Inorder traversal. Alternatively, we can check if it is the first time to visit a node for that level.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        ans = []
        data = defaultdict(int)
        def dfs(root, lvl):
            if not root:
                return
            dfs(root.left, lvl + 1)
            if lvl not in data: 
                # only update the level if it is the first node (left most)
                data[lvl] = root.val
            dfs(root.right, lvl + 1)
        dfs(root, 0)
        for i in sorted(data.keys()):
            ans.append(data[i])
        return ans
# 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
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        ans = []
        data = defaultdict(int)
        def dfs(root, lvl):
            if not root:
                return
            dfs(root.left, lvl + 1)
            if lvl not in data: 
                # only update the level if it is the first node (left most)
                data[lvl] = root.val
            dfs(root.right, lvl + 1)
        dfs(root, 0)
        for i in sorted(data.keys()):
            ans.append(data[i])
        return ans

Both DFS and BFS take O(N) time to traverse the binary tree and O(N) space requirement either queue in BFS or stack in DFS.

Left or Right Side View of a Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading…

1046 words
Last Post: Teaching Kids Programming – Counting the Number of Squares and Rectangles of a NxN Rubik Cube
Next Post: Teaching Kids Programming – Pass by Values, References or Object-References in Python

.

Leave a Comment