Intuition
-
brute_force approach includes finding the height of Tree and then traversing the Tree and printing the nodes level wise. One other challenge here can be determining the level of nodes when traversing through them.
-
Other approach using Queue, We need to visit the nodes in a lower level before any node in a higher level, this idea is quite similar to that of a queue. Push the nodes of a lower level in the queue. When any node is visited, pop that node from the queue and push the child of that node in the queue. This ensures that the node of a lower level are visited prior to any node of a higher level.
-
What do above mean?
Striver series notes
- Two array need to be created, one temporary to store elements and other to store levels.
- To determine the how many elements each level has the size of queue can be used, like done here,
Code
- Take from attempt 🏹
Attempt 1
- Worked fine in first attempt.
'''
approach:
level order traversal will be covering root node then immediate child of root node and so on
put the root node in a queue
start looping through queue and keep pushing left and right value in every iteration
keep another array to push the layers after every iteration
the queue length will change based on number of children of previous nodes
'''
from collections import deque
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == [] or root == None:
return []
q = deque()
q.append(root)
layers = []
while q:
temp = []
for el in range(len(q)):
cur = q.popleft()
temp.append(cur.val)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
layers.append(temp)
return layers
Questions
- Q. What is the difference in Level order traversal- Binary Tree traversal and Zig-Zag traversal? Ans. The direction will change in Zig-Zag traversal after every level. So there will an additional flag required. Zig Zag or Spiral traversal in Binary Tree. Q. Will