Home » C++ programs

C++ program to check whether a given Binary Search Tree is balanced or not?

Here, we are going to implement a C++ program that will check whether a given binary search tree is a balanced tree or not?
Submitted by Bhanu Pratap Raghav, on December 10, 2018

Description: Solution to check the given Binary Search tree is balanced or not.

Problem Statement: Write a program that accepts input from user to form a binary search tree and check whether the formed tree is balanced or not.

Example 1:

Input: 2 1 3 4 5 -1

BST 1

Output: Given BST is Balanced : False

Example 2:

Input: 2 1 3 4 -1

BST 2

Output: Given BST is Balanced : True

Explanation...

What do you mean by height of a tree?

A height of a tree is the largest number of edges in a path from node to a leaf node. If a tree has only one node: i.e. root node itself then the height of tree is 0.

Example:

BST 0

Height of tree: 2 ( maximum 2 edges from root to leaf)

Check when tree is balanced:

A non-empty binary search tree is said to be balanced if:

  1. Its left subtree is balanced.
  2. Its Right subtree is balanced.
  3. The difference between heights of left and right subtree is less than or equal to 1.

Example:

BST 0-1

At root height of left subtree is 1 , whereas height of right subtree is 3

Difference = 3-1=2 (which is greater than 1) i.e. Tree is not balanced.

Algorithm:

  1. Set root=root of given binary search tree.
  2. Set leftHt= height of left subtree.
  3. Set rightHt= height of right subtree.
  4. if abs(leftHt – rightHt ) > 1
    return false;
    else isHeightBalanced(root->left) &&isHeightBalanced(root->right)

C++ Code

#include <iostream>
#include <cmath>

using namespace std;

class TreeNode {
	public:
		int data;
		TreeNode* left;
		TreeNode* right;
		TreeNode(int d) {
			data = d;
			left = NULL;
			right = NULL;
		}
};

TreeNode* insertInBST(TreeNode* root, int x) {
	if (root == NULL) {
		TreeNode* tmp = new TreeNode(x);
	return tmp;
}

if (x < root->data) {
	root->left = insertInBST(root->left , x);
		return root;
	} else {
		root->right = insertInBST(root->right, x);
		return root;
	}
}

TreeNode* createBST() {
	TreeNode* root = NULL;
	int x;
	cin >> x;

	//Take input until user inputs -1
	while (true) {
		if (x == -1) break;
		root = insertInBST(root, x);
		cin >> x;
	}
	return root;
}

//Calculate height of tree with given root
int height(TreeNode* root) {
	if (root == NULL) return 0;

	int leftHt = height(root->left);
	int rightHt = height(root->right);
	int curHt = max(leftHt, rightHt) + 1;
	return curHt;
}

//Check whether tree is balanced or not
bool isHeightBalanced(TreeNode* root) {
	if (!root) {
		return true;
	}

	int leftHt = height(root->left);
	int rightHt = height(root->right);

	if (abs(leftHt - rightHt) > 1) 
			return false;
	return isHeightBalanced(root->left) && isHeightBalanced(root->right);
}

int main() {
	//Input BST
	cout<<"Input Tree elements : ";
	TreeNode* root = createBST();

	cout << "Given BST is Balanced : ";
	if (isHeightBalanced(root)) {
		cout << "True";
	}
	else {
		cout << "False";
	}

	return 0;
}

Output

First run:
Input Tree elements(stop taking input when  -1 encountered) : 2 1 3 4 5 -1
Given BST is Balanced : False

Second run:
Input Tree elements(stop taking input when  -1 encountered) : 2 1 3 4  -1
Given BST is Balanced : True





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.




Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.