CB_HackerBlocks_Problem/BinaryTree_IsTreeBalance.cpp at master · abhijeetgu/CB_HackerBlocks_Problem · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include<cmath>

using namespace std;

class node{
    public:
        int data;
        node*left;
        node*right;

        node(int d){
            data = d;
            left = NULL;
            right = NULL;
        }
};
node* buildTree(){
    int d;
    cin>>d;

    if(d==-1){
        return NULL;
    }
    node * root = new node(d);
    root->left = buildTree();
    root->right = buildTree();
    return root;
}

//Is Tree is Balanced>>>>|h1-h2|<=1
class HBpair
{
public:
    int height;
    bool balance;
};
HBpair isTreeBalance(node* root)
{
    HBpair p;
    if(root==NULL)
    {
        p.height=0;
        p.balance=true;
        return p;
    }
    //Recursive Case

    HBpair left=isTreeBalance(root->left);
    HBpair right=isTreeBalance(root->right);

    p.height=max(left.height,right.height)+1;

    if(abs(left.height-right.height)<=1 && left.balance && right.balance )
    {
        p.balance=true;
    }
    else
    {
        p.balance=false;
    }
    return p;

}

int main(){
    node* root = buildTree();
    if(isTreeBalance(root).balance)
    {
        cout<<"Balance"<<endl;
    }
    else
    {
        cout<<"Not Balance"<<endl;
    }

return 0;
}