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

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

March 22, 2022 No Comments algorithms, BFS, DFS, python, recursive, teaching kids programming, youtube video

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].

binary-tree-max-value Teaching Kids Programming - Left/Right Side View of a Binary Tree using Depth/Breadth First Search Algorithms algorithms BFS DFS python recursive teaching kids programming youtube video

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 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 e.g. 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...
1008 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

The Permanent URL is: Teaching Kids Programming – Left/Right Side View of a Binary Tree using Depth/Breadth First Search Algorithms

Related posts:

  1. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  2. Teaching Kids Programming – Algorithms to Find the Lowest Common Ancestor of a Binary Search Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given a binary search tree (BST),...
  3. The Young Prompt Engineers My sons were excited to show me the Text to Image feature using Microsoft Bing....
  4. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  5. Teaching Kids Programming – Recursive Algorithm to Prune a Binary Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  6. Teaching Kids Programming – How to Check if Two Strings Anagrams? Teaching Kids Programming: Videos on Data Structures and Algorithms Anagrams are strings/words that contain the...
  7. How to Determine Sum of Two Square Numbers? Given a non-negative integer c, your task is to decide whether there’re two integers a...
  8. The Secure Shell (SSH) Chrome Extension developed by Google Speaking about SSH tools, we often use the PuTTY or Termius, which are heavy weight...

Leave a Reply