BST - Check if a Binary Tree is Binary Search Tree or Not? - Data Structures & Algorithms 2016

In this lesson, we have written a program in C/C++ to verify whether a given binary tree is binary search tree or not.

A binary tree is called a height balanced binary tree if it satisfies the following condition -

For all nodes of the tree, absolute difference between heights of left sub-tree and right sub-tree is not greater than 1.

This algorithm is basically a modified post-order traversal where we first check that for a given node, if the left sub-tree is height balanced, then we check if the right sub-tree is height balanced and finally we check if the tree is balanced at the current node itself. In this algorithm, to indicate that the tree is not balanced at the current node to the calling function, we return value -1. In case the tree rooted at the current node is height balanced, we return the height of tree rooted at current node to the calling function. This height would then be used by calling function to determine height balance at its level. The height of the tree rooted at current node is calculated as: 1 + maximum of(height of left sub-tree, height of right sub-tree)

Let's look at the steps involved in this recursive algorithm. If a call is made to function checkBalance(currentNode) then -

1. If currentNode is null, return height as 0. This indicates that a null tree is balanced with height of 0. This would be the base case for this algorithm.

2. We check if left sub-tree is balanced by making a recursive call: leftSubtreeHeight = checkBalance(currentNode.left)

If left sub-tree is not balanced, we return -1 to indicate that the tree rooted at currentNode is unbalanced as well.

3. We check if right sub-tree is balanced by making a recursive call: rightSubtreeHeight = checkBalance(currentNode.right)

If right sub-tree is not balanced, we return -1 to indicate that the tree rooted at currentNode is unbalanced as well.

4. If both left and right sub-trees are balanced, we check the balance of the tree at the currentNode by checking absolute difference of leftSubtreeHeight and rightSubtreeHeight. If it is greater than 1, then we return -1 to indicate imbalance.

5. If the tree is balanced at the currentNode as well, then we return height of the tree at the currentNode by returning (Math.max(leftSubtreeHeight, rightSubtreeHeight) + 1).

Check out function checkBalance(TreeNode currentNode) in the code snippet for implementation.

Time complexity of this algorithm is O(n) in worst case.

Don't Forget to Subscribe Our Channel For more Software related videos.

https://www.youtube.com/channel/UCvtgPQq67sRfz3m2T_OrIWA

Our Facebook Page

https://www.facebook.com/Tuts-Online-1175068025891211/

Our Google+

https://plus.google.com/u/0/b/106482468968232599840/106482468968232599840/

Follows us on Our Twitter Account

https://twitter.com/mughal_zeeshi

Official Blog

https://tutsonline1.blogspot.com/