**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