Level order printing of Binary Search Tree

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

level order printing of BST
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.

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 

Algorithm of first approach to print level order

  1. Start from the root
  2. Add root to queue. 
  3. Take the node out from the queue, and add left and right child of the root to queue.
  4. 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).

Print Paths in Binary Search Tree

Print paths in binary search tree

Path in a tree is list of nodes from root to leaf. There can be many paths in a tree, maximum length of a path can be N nodes in worst case, in average case it would be logN. Consider following tree:

print paths with given sum in binary tree

Paths is above tree are :10,6,4
10,6,7
10,15,13
10,15,17

To traverse a path, we start at root. At every node we have two options, either we go left or we go right.  We traverse left first till the we have covered all paths which are on the left side of the node, then we come back to node and traverse all paths which are on the right side.  It is plain traversing of all nodes, only thing is we need to do is some book keeping so that we can print the path when we reach a leaf node.

Algorithm to print paths in binary tree

1. Start from root, add node to path

2. Traverse all paths in left sub tree 
3. Traverse all paths in right sub tree 

Code
Complexity analysis
Since we are traversing each node at least once, complexity of this code is O(N).


Output of the code for following tree

print path in binary tree
Input Binary search tree

Path : 30, 20, 10, 12, 

Path : 30, 40, 37, 
Path : 30, 40, 45, 

Print all paths with a given sum in BST

Let’s consider a problem where we need to print only those paths which sums up to a given number.
Basic algorithms remains same only thing we add is to keep track of sum of nodes and before printing check if the sum of all nodes in path is equal to given number.

Algorithm to print paths with given sum

1. Start from root.
2. Subtract root value from given number, say it as subsum
3. Check all path in left sub tree for sum as subsum
4. Check all paths in right sub tree for sum as subsum
5. If subsum at leaf is zero, print the path
Code

Complexity analysis
Since we are traversing each node at least once, complexity of algorithm to print paths with given sum is O(N).  Following code implements another similar problem where we need to just find whether BST contains a path with given sum.

Driver program for all above functions is, change the function call 🙂

We have seen three versions of problem of printing paths in binary search tree and similar approach used for the solution.

Check if binary tree is Binary Search Tree (BST) or not?

Find if binary tree is binary search tree or not.

This is one of the most asked programming interview question.How to check or validate that a given binary tree is a binary search tree (BST)?

Binary search tree property
All the nodes on the left side of a given node are smaller and all on the right side are greater than the given node. So, essentially, any tree is a binary search tree if both its left sub tree and right sub tree are BST and root satisfy above condition.
Binary tree is Binary Search Tree (BST) if
1. Left sub tree is BST
2. Right sub tree is BST
3. Value of root is greater than max in left sub tree and less than minimum in right sub tree
Following figure explains which is binary search tree and which is not.

Check if tree is binary search tree


No further analysis is required for this problem.

Notes :
I have gone through codes which are simpler but are based on assumption regarding the range of data in tree. This code is generic and does not make any assume anything about data in tree.
Some implementations do the check for root first and then go forward to check it for left and right sub tree. In that case, they could not use the information that both left and right sub tree are Binary Search Tree while finding max and minimum in those trees. Above implementation uses that information.

Watch video here


Implementation of find_maximum and find_minimum can be found in this post

Code of checking if binary tree is binary search tree

Above code is correct but inefficient because for every node check, its left and right sub tree needs to be traversed and max and min needs to be found. It make algorithm complexity of O(n2).
There is another method where we use the same min and max concept, however keeping track of the max which needs to be there on left side and minimum on the right side. Start from INT_MAX and INT_MIN, check if the root node is greater than max and less than the min. If yes, than go down left subtree with max changed to root value, and go down to right subtree with min changed to root value. By doing so, we are applying the same method as above that minimum node in right side should be greater than root and maximum in the left side should be less than root value.Code below implements this method

Complexity of above implementation is O(n) as we are traversing each node only once.
There is another method to find if binary tree is binary search tree or not. That is to do inorder traversal of binary tree and keep track of previous node. As we know inorder traversal of a binary search tree gives us elements in sorted order, previously visited node should be always smaller than the current node. If all nodes satisfy this property, binary tree is binary search tree. And as soon as this property is violated at any node, we can say tree is not a binary search tree. 
Complexity of this implementation is also O(n) as we will be traversing each node only once. Code snippet for above method:

Test cases

1. A BST as an input
2. A non BST as an input
3. A null tree
4. A tree where left sub tree of root is BST but max in left tree is greater than root.
5. Same as 4 where minimum in right sub tree is less than root.