# Level order printing of binary search tree

Print nodes of a tree level wise i.e. nodes at same level should be printed together.

For example, in following tree output should be 10,6,15,4,7,13,17

Binary Search Tree |

### Analysis

**Level order printing of BST**can be solved in two ways, in one way we need to maintain an auxiliary data structure to store nodes at a given level. Second way is to use recursion.

Let’s see the second way first as this is easy to understand and implement.

Since we need to print nodes level wise, we need to figure out height of the tree. Once we have height, go to every level less than height and print nodes at that level.

At every node, keep track of level we are at in the tree. So at root, we start with desired level. As we move down, we decrement the level by one. Once current level becomes 1, node is at the desired level and hence printed.

This step can be implemented in recursive way. Base case for recursion is evident from above discussion i.e when level is equal to 1, print node and return. Otherwise, recurs with level count one less.

For example in tree given above if we want to print nodes at level 2, we call function as print_level(root, 2) and decrement count every time we call print_level. When count becomes one, we print the node.

At every node, keep track of level we are at in the tree. So at root, we start with desired level. As we move down, we decrement the level by one. Once current level becomes 1, node is at the desired level and hence printed.

This step can be implemented in recursive way. Base case for recursion is evident from above discussion i.e when level is equal to 1, print node and return. Otherwise, recurs with level count one less.

For example in tree given above if we want to print nodes at level 2, we call function as print_level(root, 2) and decrement count every time we call print_level. When count becomes one, we print the node.

## Algorithm to print BST level wise

1. Find the height of the tree.

2. For each level print nodes as below.

3. Start from the root for each level.

4. Decrement the level count.

5. If level count is one, print the node.

6. Else move down the tree.

### Code

Output for the tree given below is

Input Binary search tree |

Level 1 :30

Level 2 :20 40

Level 3 :10 37 45

Level 4 :12

Level 3 :10 37 45

Level 4 :12

## Algorithm of first approach to print level order

- Start from the root
- Add root to queue.
- Take the node out from the queue, and add left and right child of the root to queue.
- Print node and repeat step 3.

### Code

Output for above given tree will be

30

adding left and right of 30

20

adding left and right of 20

40

adding left and right of 40

10

adding left and right of 10

37

adding left and right of 37

45

adding left and right of 45

12

adding left and right of 12

### Complexity analysis

Since we would be traversing each node of the tree, time complexity would be of order N i.e.O(N).

In the first case, since we would be traversing N for every level we print, so complexity comes O(NlogN).