Sunday, December 28, 2014

A function to check if a binary tree is balanced.

Q. Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two sub trees of any node never differ by more than one.

Algorithm:

1. Go to the left in tree.
2. If a null is encountered, return 0.
3. Returned value is incremented (this is representing the height at that level).
4. Recursively go to the right in sub trees.
5. Return height from right sub tree.
6. If difference between heights is between [-1 to 1] then return the max of heights of left and right else return -1(unacceptable height) and stop further evaluation. (Since if a sub tree is unbalanced, so it the whole tree).

Source:

class Tree{
     
    class Node{
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    Node root;
    
    void buildTree(){
        root = new Node(3);
        root.right = new Node(2);
        root.left = new Node(1);
        Node l = root.left;
        l.left = new Node(4);
        l.right = new Node(5);
        l.right.right = new Node(1772);
        l.right.left = new Node(89);
        
        root.right.left = new Node(88);
    }
    
    boolean checkBalanced(){
        return checkB(root)!=-1;
    }
    
    int checkB(Node node){
        if(node == null)return 0;
        int left = checkB(node.left)+1; if(left == 0)return -1;
        int right = checkB(node.right)+1; if(right == 0)return -1;
        int diff = Math.abs(left - right); if(diff > 1)return -1;
        else return Math.max(left, right);
    }
    
    public static void main(String[] args){
        Tree t = new Tree();
        t.buildTree();
        System.out.println(t.checkBalanced());
    }
}

Output:

true

No comments:

Post a Comment