Implement this design using the Deque
Explore ways to perform a Level Order Traversal on a
Binary Tree.
Implement this design using the Deque
The root element of the binary tree is given to you. Your task is to return
the level order traversal of the Binary Tree’s nodes’ values – from left to right,
level by level.
# Class to represent Tree node
class Node:
# A function to create a new node
def __init__(self, key):
self.data = key
self.left = None
self.right = None
Below is an illustrated sample of Binary Tree nodes for your reference, which
in-fact is the same example we discussed in the lecture.
root = Node(4)
root.left = Node(2)
root.right = Node(6)
root.left.left = Node(1)
root.left.right = Node(3)
root.right.left = Node(5)
root.right.right = Node(7)
Your code will need to return all the nodes of the Binary Tree in Level Order
Traversal fashion - from left to right. That is: 4 2 6 1 3 5 7
Level Order Tree Traversal with the help of the Queue data-structure should
meet the following complexities as stated below.
Time Complexity: O(n)
Space Complexity: O(n)
Step by step
Solved in 4 steps with 2 images
