Q:

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

belongs to collection: C++ programs on various topics

mahmoud2506
Save to bookmark
|
2022-05-05
|
  181 
0

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

C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-05
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

C++ programs on various topics
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Append Last N Nodes to First in the Linked List us... >>
<< C++ program to obtain Multiplication recursively...