Binary tree are the tree where one node can have only two child and cannot have more than two.
Level order traversal of a binary tree.
Level order traversal means that we visit the nodes level by level. Like for below tree the level order traversal will be
Its Level order traversal will be
1 2 3 4 5
Here is the code for doing that.
class Node: def __init__(self,data): self.left = None self.right = None self.data = data def level_order(queue): if len(queue) == 0: return node = queue queue.pop(0) if node.left: queue.append(node.left) if node.right: queue.append(node.right) print node.data level_order(queue) queue = list() root = Node(1) queue.append(root) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) level__order(queue) # 1 2 3 4 5
What we did here:
We make use of queues to do the level order traversal. What we did is we visit a node and put its left and right child in the queue and delete the current node. In this way we visit the tree in level order.
Wanna read more about Algorithms and Data structures visit below link.
Algorithms and Data Structures.
Please share and subscribe.