For a binary tree to be a binary search tree (BST), the data of all the nodes in the left sub-tree of the root node should be
less than or equals to the data of the root. The data of all the nodes in the right subtree of the root node should be greater
than the data of the root. This example shows the implementation of a binary search tree level order traversal (breadth first).
What is Level order traversal (breadth first)?
In Level order traversal, we visit every node on a level before going to a lower level from
left to right. This is also known as Breadth first traversal as the search tree is broadened as much as possible on each depth
before going to the next depth. Below picture shows the level order traversal.
Here is an example picture of binary search tree (BST) for our example code:
Here is the steps to implement Level order traversal:
- Since we have to traverse in same level until we cover all nodes in the same level, it is hard to keep the node references, we
will maintain a queue for storing all discovered nodes.
- Initially the queue will be empty.
- If the root node is not null, push it to the queue.
- Use a while loop to visit all nodes in the queue until the queue is empty.
- Inside while loop, pop out the node.
- Add the left node to the queue if it is not null.
- Add the right node to the queue if it is not null.
- Read the node data and display it.
- Repeat from step 5, until the queue is empty.