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 10 / \ 5 3 \ 1Output:
[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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | # 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 |
# 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 ansThe 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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # 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 |
# 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 ansBy 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) —
loading...
Last Post: Generate the Power SubSet using Depth First Search Algorithm
Next Post: Improved Depth First Search Algorithm to Generate Combinations of Parentheses
