Solution
#include <iostream>
using namespace std;
typedef struct binary_tree{
int data;
struct binary_tree *left;
struct binary_tree *right;
}bin_tree;
bin_tree* create_bt(int data)
{
bin_tree *bt;
bt = new bin_tree;
bt->data = data;
bt->left = NULL;
bt->right = NULL;
return bt;
}
bool add_bt(bin_tree* parent, bin_tree* child, int isleft)
{
if(NULL == parent){
cout << "parent cannot be NULL in adding a child" << endl;
return false;
}
if(isleft == 1){
parent->left = child;
}
else{
parent->right = child;
}
return true;
}
bool del_bt(bin_tree* parent)
{
if(parent == NULL){
cout << "tree is already NULL" << endl;
return false;
}
if(parent->left == NULL && parent->right == NULL){
cout << parent << "with data" << parent->data << "is being deleted!" << endl;
return true;
}
if(parent->left != NULL){
del_bt(parent->left);
}
if(parent->right != NULL){
del_bt(parent->right);
}
return true;
}
int bt_max_len(bin_tree* parent)
{
if(parent->left == NULL && parent->right == NULL)
return 0;
if(parent->left != NULL && parent->right == NULL)
return 1 + bt_max_len(parent->left);
if(parent->left == NULL && parent->right != NULL)
return 1 + bt_max_len(parent->right);
return max(bt_max_len(parent->left), bt_max_len(parent->right)) + 1;
}
int bt_min_len(bin_tree* parent)
{
if(parent->left == NULL && parent->right == NULL)
return 0;
if(parent->left != NULL && parent->right == NULL)
return bt_min_len(parent->left);
if(parent->left == NULL && parent->right != NULL)
return bt_min_len(parent->right);
return min(bt_min_len(parent->left), bt_min_len(parent->right)) + 1;
}
bool is_bt_balanced(bin_tree* parent)
{
return (bt_max_len(parent) - bt_min_len(parent) > 1) ? false : true;
}
int main(int argc, char* argv[])
{
bin_tree *p;
bin_tree *c0;
bin_tree *c1;
bin_tree *c2;
bin_tree *c3;
p = create_bt(0);
c0 = create_bt(1);
add_bt(p, c0, 1);
c1 = create_bt(2);
add_bt(p, c1, 0);
c2 = create_bt(3);
add_bt(c0, c2, 1);
c3 = create_bt(4);
add_bt(c0, c3, 0);
cout << "max len is " << bt_max_len(p) << endl;
cout << "min len is " << bt_min_len(p) << endl;
return 0;
}
Output
Problem
Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.