CareerCup_4.1@1point3acres

main.cpp

/*****************************************************************

    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
    
 ******************************************************************/
    
#include <iostream>

struct Node {
    int data;
    Node *lchild;
    Node *rchild;
    Node(int d = 0): data(d), lchild(nullptr), rchild(nullptr){}
};


int isBalanced(Node *head) {
    if(head == nullptr)
        return 0;
    int lheight = isBalanced(head->lchild);
    int rheight = isBalanced(head->rchild);
    if(lheight == -1 || rheight == -1)
        return -1;
    else if(abs(lheight - rheight) > 1)
        return -1;
    else
        return lheight > rheight ? lheight + 1 : rheight + 1;
}

void constructTree(Node *head) {
    head->lchild = new Node(2);
    head->lchild->lchild = new Node(3);
    head->rchild = new Node(4);
}

int main() {
    Node *head = new Node(1);
    constructTree(head);
    int ans = isBalanced(head);
    if(ans == -1)
        std::cout << "unbalance." << std::endl;
    else
        std::cout << "balance" << std::endl;
    return 0;
}