Teaching Kids Programming – The Left Side View of Binary Tree via Breadth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, return the leftmost node’s value on each level of the tree.

Constraints
n ≤ 100,000 where n is the number of nodes in root
Example 1

   0
  / \
 5   3
      \
       1

Output:
[0, 5, 1]

Compute the Left Side View of a Binary Tree via BFS Algorithm

The BFS (Breadth First Search) Algorithm performs a level-by-level traversal on a tree/grahp. We can use BFS to store only the first node in every level. To accomplish this, we need to expand all nodes of the same level at once.

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def leftSideView(self, root):
        if root is None:
            return []
        q = deque([root])
        ans = []
        while len(q) > 0:
            sz = len(q)
            for i in range(sz):
                p = q.popleft()
                if p.left:
                    q.append(p.left)
                if p.right:
                    q.append(p.right)
                if i == 0:
                    ans.append(p.val)
        return ans

The time complexity of BFS is usually O(N) where N is the number of the nodes in the given binary tree. And the space complexity is O(N) as we are using a queue.

See also: Depth First Search and Breadth First Search Algorithm to Compute the Left Side View of a Binary Tree

We can move the if-condition check outside – by directly appending the first in each level to the result:

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def leftSideView(self, root):
        if root is None:
            return []
        q = deque([root])
        ans = []
        while len(q) > 0:
            sz = len(q)
            ans.append(q[0].val)
            for i in range(sz):
                p = q.popleft()
                if p.left:
                    q.append(p.left)
                if p.right:
                    q.append(p.right)
        return ans

By changing q[0].val to q[-1].val we are getting the Right-side view instead.

Left or Right Side View of a Binary Tree

• Teaching Kids Programming – The Left Side View of Binary Tree via Breadth First Search Algorithm
• Depth First Search and Breadth First Search Algorithm to Compute the Left Side View of a Binary Tree
• Teaching Kids Programming – Left/Right Side View of a Binary Tree using Depth/Breadth First Search Algorithms

–EOF (The Ultimate Computing & Technology Blog) —