Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Check if a Binary Tree is balanced
public class IsTreeBalanced {
public static void main(String[] args) {
// build a tree with Nodes...root is root Node
isBalanced(root);
}
public static int getHeight(Node root) {
// base case, bottom of sub tree
if (root == null) {
return 0;
}
// get height of left subtree, and check if it is balanced
int heightLeft = getHeight(root.left);
if (heightLeft == -1) {
return -1;
}
// get height of right subtree, and check if it is balanced
int heightRight = getHeight(root.right);
if (heightRight == -1) {
return -1;
}
// get difference between left and right, if > 1 they are unbalanced
int heightDiff = Math.abs(heightRight - heightLeft);
if (heightDiff > 1)
return -1;
else
return Math.max(heightLeft, heightRight) + 1;
}
public static void isBalanced(Node root) {
if (getHeight(root) == -1) {
System.out.println("Tree not balanced");
return;
} else {
System.out.println("Tree IS balanced!");
}
}
}
class Node {
int data;
public Node left;
public Node right;
public Node(int n) {
data = n;
left = null;
right = null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.