It's been a while from those school years. Got a job as IT specialist at a hospital. Trying to move to do some actual programming now. I'm working on binary trees now, and I was wondering what would be the best way to determine if the tree is height-balanced.
I was thinking of something along this:
public boolean isBalanced(Node root){
if(root==null){
return true; //tree is empty
}
else{
int lh = root.left.height();
int rh = root.right.height();
if(lh - rh > 1 || rh - lh > 1){
return false;
}
}
return true;
}
Is this a good implementation? or am I missing something?
This question is related to
java
algorithm
data-structures
binary-tree
Balance is a truly subtle property; you think you know what it is, but it's so easy to get wrong. In particular, even Eric Lippert's (good) answer is off. That's because the notion of height is not enough. You need to have the concept of minimum and maximum heights of a tree (where the minimum height is the least number of steps from the root to a leaf, and the maximum is... well, you get the picture). Given that, we can define balance to be:
A tree where the maximum height of any branch is no more than one more than the minimum height of any branch.
(This actually implies that the branches are themselves balanced; you can pick the same branch for both maximum and minimum.)
All you need to do to verify this property is a simple tree traversal keeping track of the current depth. The first time you backtrack, that gives you a baseline depth. Each time after that when you backtrack, you compare the new depth against the baseline
In code:
class Tree {
Tree left, right;
static interface Observer {
public void before();
public void after();
public boolean end();
}
static boolean traverse(Tree t, Observer o) {
if (t == null) {
return o.end();
} else {
o.before();
try {
if (traverse(left, o))
return traverse(right, o);
return false;
} finally {
o.after();
}
}
}
boolean balanced() {
final Integer[] heights = new Integer[2];
return traverse(this, new Observer() {
int h;
public void before() { h++; }
public void after() { h--; }
public boolean end() {
if (heights[0] == null) {
heights[0] = h;
} else if (Math.abs(heights[0] - h) > 1) {
return false;
} else if (heights[0] != h) {
if (heights[1] == null) {
heights[1] = h;
} else if (heights[1] != h) {
return false;
}
}
return true;
}
});
}
}
I suppose you could do this without using the Observer pattern, but I find it easier to reason this way.
[EDIT]: Why you can't just take the height of each side. Consider this tree:
/\
/ \
/ \
/ \_____
/\ / \_
/ \ / / \
/\ C /\ / \
/ \ / \ /\ /\
A B D E F G H J
OK, a bit messy, but each side of the root is balanced: C is depth 2, A, B, D, E are depth 3, and F, G, H, J are depth 4. The height of the left branch is 2 (remember the height decreases as you traverse the branch), the height of the right branch is 3. Yet the overall tree is not balanced as there is a difference in height of 2 between C and F. You need a minimax specification (though the actual algorithm can be less complex as there should be only two permitted heights).
Well, you need a way to determine the heights of left and right, and if left and right are balanced.
And I'd just return height(node->left) == height(node->right);
As to writing a height function, read:
Understanding recursion
#include <iostream>
#include <deque>
#include <queue>
struct node
{
int data;
node *left;
node *right;
};
bool isBalanced(node *root)
{
if ( !root)
{
return true;
}
std::queue<node *> q1;
std::queue<int> q2;
int level = 0, last_level = -1, node_count = 0;
q1.push(root);
q2.push(level);
while ( !q1.empty() )
{
node *current = q1.front();
level = q2.front();
q1.pop();
q2.pop();
if ( level )
{
++node_count;
}
if ( current->left )
{
q1.push(current->left);
q2.push(level + 1);
}
if ( current->right )
{
q1.push(current->right);
q2.push(level + 1);
}
if ( level != last_level )
{
std::cout << "Check: " << (node_count ? node_count - 1 : 1) << ", Level: " << level << ", Old level: " << last_level << std::endl;
if ( level && (node_count - 1) != (1 << (level-1)) )
{
return false;
}
last_level = q2.front();
if ( level ) node_count = 1;
}
}
return true;
}
int main()
{
node tree[15];
tree[0].left = &tree[1];
tree[0].right = &tree[2];
tree[1].left = &tree[3];
tree[1].right = &tree[4];
tree[2].left = &tree[5];
tree[2].right = &tree[6];
tree[3].left = &tree[7];
tree[3].right = &tree[8];
tree[4].left = &tree[9]; // NULL;
tree[4].right = &tree[10]; // NULL;
tree[5].left = &tree[11]; // NULL;
tree[5].right = &tree[12]; // NULL;
tree[6].left = &tree[13];
tree[6].right = &tree[14];
tree[7].left = &tree[11];
tree[7].right = &tree[12];
tree[8].left = NULL;
tree[8].right = &tree[10];
tree[9].left = NULL;
tree[9].right = &tree[10];
tree[10].left = NULL;
tree[10].right= NULL;
tree[11].left = NULL;
tree[11].right= NULL;
tree[12].left = NULL;
tree[12].right= NULL;
tree[13].left = NULL;
tree[13].right= NULL;
tree[14].left = NULL;
tree[14].right= NULL;
std::cout << "Result: " << isBalanced(tree) << std::endl;
return 0;
}
public boolean isBalanced(TreeNode root)
{
return (maxDepth(root) - minDepth(root) <= 1);
}
public int maxDepth(TreeNode root)
{
if (root == null) return 0;
return 1 + max(maxDepth(root.left), maxDepth(root.right));
}
public int minDepth (TreeNode root)
{
if (root == null) return 0;
return 1 + min(minDepth(root.left), minDepth(root.right));
}
If binary tree is balanced or not can be checked by Level order traversal:
private boolean isLeaf(TreeNode root) {
if (root.left == null && root.right == null)
return true;
return false;
}
private boolean isBalanced(TreeNode root) {
if (root == null)
return true;
Vector<TreeNode> queue = new Vector<TreeNode>();
int level = 1, minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;
queue.add(root);
while (!queue.isEmpty()) {
int elementCount = queue.size();
while (elementCount > 0) {
TreeNode node = queue.remove(0);
if (isLeaf(node)) {
if (minLevel > level)
minLevel = level;
if (maxLevel < level)
maxLevel = level;
} else {
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
elementCount--;
}
if (abs(maxLevel - minLevel) > 1) {
return false;
}
level++;
}
return true;
}
Post order solution, traverse the tree only once. Time complexity is O(n), space is O(1), it's better than top-down solution. I give you a java version implementation.
public static <T> boolean isBalanced(TreeNode<T> root){
return checkBalance(root) != -1;
}
private static <T> int checkBalance(TreeNode<T> node){
if(node == null) return 0;
int left = checkBalance(node.getLeft());
if(left == -1) return -1;
int right = checkBalance(node.getRight());
if(right == -1) return -1;
if(Math.abs(left - right) > 1){
return -1;
}else{
return 1 + Math.max(left, right);
}
}
/* Returns true if Tree is balanced, i.e. if the difference between the longest path and the shortest path from the root to a leaf node is no more than than 1. This difference can be changed to any arbitrary positive number. */
boolean isBalanced(Node root) {
if (longestPath(root) - shortestPath(root) > 1)
return false;
else
return true;
}
int longestPath(Node root) {
if (root == null);
return 0;
else {
int leftPathLength = longestPath(root.left);
int rightPathLength = longestPath(root.right);
if (leftPathLength >= rightPathLength)
return leftPathLength + 1;
else
return rightPathLength + 1;
}
}
int shortestPath(Node root) {
if (root == null);
return 0;
else {
int leftPathLength = shortestPath(root.left);
int rightPathLength = shortestPath(root.right);
if (leftPathLength <= rightPathLength)
return leftPathLength + 1;
else
return rightPathLength + 1;
}
}
An empty tree is height-balanced. A non-empty binary tree T is balanced if:
1) Left subtree of T is balanced
2) Right subtree of T is balanced
3) The difference between heights of left subtree and right subtree is not more than 1.
/* program to check if a tree is height-balanced or not */
#include<stdio.h>
#include<stdlib.h>
#define bool int
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* The function returns true if root is balanced else false
The second parameter is to store the height of tree.
Initially, we need to pass a pointer to a location with value
as 0. We can also write a wrapper over this function */
bool isBalanced(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;
/* l will be true if left subtree is balanced
and r will be true if right subtree is balanced */
int l = 0, r = 0;
if(root == NULL)
{
*height = 0;
return 1;
}
/* Get the heights of left and right subtrees in lh and rh
And store the returned values in l and r */
l = isBalanced(root->left, &lh);
r = isBalanced(root->right,&rh);
/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = (lh > rh? lh: rh) + 1;
/* If difference between heights of left and right
subtrees is more than 2 then this node is not balanced
so return 0 */
if((lh - rh >= 2) || (rh - lh >= 2))
return 0;
/* If this node is balanced and left and right subtrees
are balanced then return true */
else return l&&r;
}
/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
int height = 0;
/* Constructed binary tree is
1
/ \
2 3
/ \ /
4 5 6
/
7
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->left->left->left = newNode(7);
if(isBalanced(root, &height))
printf("Tree is balanced");
else
printf("Tree is not balanced");
getchar();
return 0;
}
Time Complexity: O(n)
public int height(Node node){
if(node==null)return 0;
else{
int l=height(node.leftChild);
int r=height(node.rightChild);
return(l>r?l+1:r+1);
}}
public boolean balanced(Node n){
int l= height(n.leftChild);
int r= height(n.rightChild);
System.out.println(l + " " +r);
if(Math.abs(l-r)>1)
return false;
else
return true;
}
Here is a complete worked out tested solution in C# (sorry I'm no java dev) (just copy paste in console app). I know that definition of balanced varies so not everyone may like my test results but please just look at the slightly different approach of checking depth/height in a recursive loop and exiting on the first mismatch without saving node height/level/depth on each node (only maintaining it in a function call).
using System;
using System.Linq;
using System.Text;
namespace BalancedTree
{
class Program
{
public static void Main()
{
//Value Gathering
Console.WriteLine(RunTreeTests(new[] { 0 }));
Console.WriteLine(RunTreeTests(new int[] { }));
Console.WriteLine(RunTreeTests(new[] { 0, 1, 2, 3, 4, -1, -4, -3, -2 }));
Console.WriteLine(RunTreeTests(null));
Console.WriteLine(RunTreeTests(new[] { 10, 8, 12, 8, 4, 14, 8, 10 }));
Console.WriteLine(RunTreeTests(new int[] { 20, 10, 30, 5, 15, 25, 35, 3, 8, 12, 17, 22, 27, 32, 37 }));
Console.ReadKey();
}
static string RunTreeTests(int[] scores)
{
if (scores == null || scores.Count() == 0)
{
return null;
}
var tree = new BinarySearchTree();
foreach (var score in scores)
{
tree.InsertScore(score);
}
Console.WriteLine(tree.IsBalanced());
var sb = tree.GetBreadthWardsTraversedNodes();
return sb.ToString(0, sb.Length - 1);
}
}
public class Node
{
public int Value { get; set; }
public int Count { get; set; }
public Node RightChild { get; set; }
public Node LeftChild { get; set; }
public Node(int value)
{
Value = value;
Count = 1;
}
public override string ToString()
{
return Value + ":" + Count;
}
public bool IsLeafNode()
{
return LeftChild == null && RightChild == null;
}
public void AddValue(int value)
{
if (value == Value)
{
Count++;
}
else
{
if (value > Value)
{
if (RightChild == null)
{
RightChild = new Node(value);
}
else
{
RightChild.AddValue(value);
}
}
else
{
if (LeftChild == null)
{
LeftChild = new Node(value);
}
else
{
LeftChild.AddValue(value);
}
}
}
}
}
public class BinarySearchTree
{
public Node Root { get; set; }
public void InsertScore(int score)
{
if (Root == null)
{
Root = new Node(score);
}
else
{
Root.AddValue(score);
}
}
private static int _heightCheck;
public bool IsBalanced()
{
_heightCheck = 0;
var height = 0;
if (Root == null) return true;
var result = CheckHeight(Root, ref height);
height--;
return (result && height == 0);
}
private static bool CheckHeight(Node node, ref int height)
{
height++;
if (node.LeftChild == null)
{
if (node.RightChild != null) return false;
if (_heightCheck != 0) return _heightCheck == height;
_heightCheck = height;
return true;
}
if (node.RightChild == null)
{
return false;
}
var leftCheck = CheckHeight(node.LeftChild, ref height);
if (!leftCheck) return false;
height--;
var rightCheck = CheckHeight(node.RightChild, ref height);
if (!rightCheck) return false;
height--;
return true;
}
public StringBuilder GetBreadthWardsTraversedNodes()
{
if (Root == null) return null;
var traversQueue = new StringBuilder();
traversQueue.Append(Root + ",");
if (Root.IsLeafNode()) return traversQueue;
TraversBreadthWards(traversQueue, Root);
return traversQueue;
}
private static void TraversBreadthWards(StringBuilder sb, Node node)
{
if (node == null) return;
sb.Append(node.LeftChild + ",");
sb.Append(node.RightChild + ",");
if (node.LeftChild != null && !node.LeftChild.IsLeafNode())
{
TraversBreadthWards(sb, node.LeftChild);
}
if (node.RightChild != null && !node.RightChild.IsLeafNode())
{
TraversBreadthWards(sb, node.RightChild);
}
}
}
}
What kind of tree are you talking about? There are self-balancing trees out there. Check their algorithms where they determine if they need to reorder the tree in order to maintain balance.
Note 1: The height of any sub-tree is computed only once.
Note 2: If the left sub-tree is unbalanced then the computation of the right sub-tree, potentially containing million elements, is skipped.
// return height of tree rooted at "tn" if, and only if, it is a balanced subtree
// else return -1
int maxHeight( TreeNode const * tn ) {
if( tn ) {
int const lh = maxHeight( tn->left );
if( lh == -1 ) return -1;
int const rh = maxHeight( tn->right );
if( rh == -1 ) return -1;
if( abs( lh - rh ) > 1 ) return -1;
return 1 + max( lh, rh );
}
return 0;
}
bool isBalanced( TreeNode const * root ) {
// Unless the maxHeight is -1, the subtree under "root" is balanced
return maxHeight( root ) != -1;
}
Here is a version based on a generic depth-first traversal. Should be faster than the other correct answer and handle all the mentioned "challenges." Apologies for the style, I don't really know Java.
You can still make it much faster by returning early if max and min are both set and have a difference >1.
public boolean isBalanced( Node root ) {
int curDepth = 0, maxLeaf = 0, minLeaf = INT_MAX;
if ( root == null ) return true;
while ( root != null ) {
if ( root.left == null || root.right == null ) {
maxLeaf = max( maxLeaf, curDepth );
minLeaf = min( minLeaf, curDepth );
}
if ( root.left != null ) {
curDepth += 1;
root = root.left;
} else {
Node last = root;
while ( root != null
&& ( root.right == null || root.right == last ) ) {
curDepth -= 1;
last = root;
root = root.parent;
}
if ( root != null ) {
curDepth += 1;
root = root.right;
}
}
}
return ( maxLeaf - minLeaf <= 1 );
}
Balancing usually depends on the length of the longest path on each direction. The above algorithm is not going to do that for you.
What are you trying to implement? There are self-balancing trees around (AVL/Red-black). In fact, Java trees are balanced.
Here's what i have tried for Eric's bonus exercise. I try to unwind of my recursive loops and return as soon as I find a subtree to be not balanced.
int heightBalanced(node *root){
int i = 1;
heightBalancedRecursive(root, &i);
return i;
}
int heightBalancedRecursive(node *root, int *i){
int lb = 0, rb = 0;
if(!root || ! *i) // if node is null or a subtree is not height balanced
return 0;
lb = heightBalancedRecursive(root -> left,i);
if (!*i) // subtree is not balanced. Skip traversing the tree anymore
return 0;
rb = heightBalancedRecursive(root -> right,i)
if (abs(lb - rb) > 1) // not balanced. Make i zero.
*i = 0;
return ( lb > rb ? lb +1 : rb + 1); // return the current height of the subtree
}
This only determines if the top level of the tree is balanced. That is, you could have a tree with two long branches off the far left and far right, with nothing in the middle, and this would return true. You need to recursively check the root.left and root.right to see if they are internally balanced as well before returning true.
RE: @lucky's solution using a BFS to do a level-order traversal.
We traverse the tree and keep a reference to vars min/max-level which describe the minimum level at which a node is a leaf.
I believe that the @lucky solution requires a modification. As suggested by @codaddict, rather than checking if a node is a leaf, we must check if EITHER the left or right children is null (not both). Otherwise, the algorithm would consider this a valid balanced tree:
1
/ \
2 4
\ \
3 1
In Python:
def is_bal(root):
if root is None:
return True
import queue
Q = queue.Queue()
Q.put(root)
level = 0
min_level, max_level = sys.maxsize, sys.minsize
while not Q.empty():
level_size = Q.qsize()
for i in range(level_size):
node = Q.get()
if not node.left or node.right:
min_level, max_level = min(min_level, level), max(max_level, level)
if node.left:
Q.put(node.left)
if node.right:
Q.put(node.right)
level += 1
if abs(max_level - min_level) > 1:
return False
return True
This solution should satisfy all the stipulations provided in the initial question, operating in O(n) time and O(n) space. Memory overflow would be directed to the heap rather than blowing a recursive call-stack.
Alternatively, we could initially traverse the tree to compute + cache max heights for each root subtree iteratively. Then in another iterative run, check if the cached heights of the left and right subtrees for each root never differ by more than one. This would also run in O(n) time and O(n) space but iteratively so as not to cause stack overflow.
The definition of a height-balanced binary tree is:
Binary tree in which the height of the two subtrees of every node never differ by more than 1.
So,
An empty binary tree is always height-balanced.
A non-empty binary tree is height-balanced if:
Consider the tree:
A
\
B
/ \
C D
As seen the left subtree of A is height-balanced (as it is empty) and so is its right subtree. But still the tree is not height-balanced as condition 3 is not met as height of left-subtree is 0 and height of right sub-tree is 2.
Also the following tree is not height balanced even though the height of left and right sub-tree are equal. Your existing code will return true for it.
A
/ \
B C
/ \
D G
/ \
E H
So the word every in the def is very important.
This will work:
int height(treeNodePtr root) {
return (!root) ? 0: 1 + MAX(height(root->left),height(root->right));
}
bool isHeightBalanced(treeNodePtr root) {
return (root == NULL) ||
(isHeightBalanced(root->left) &&
isHeightBalanced(root->right) &&
abs(height(root->left) - height(root->right)) <=1);
}
Wouldn't this work?
return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );
Any unbalanced tree would always fail this.
static boolean isBalanced(Node root) {
//check in the depth of left and right subtree
int diff = depth(root.getLeft()) - depth(root.getRight());
if (diff < 0) {
diff = diff * -1;
}
if (diff > 1) {
return false;
}
//go to child nodes
else {
if (root.getLeft() == null && root.getRight() == null) {
return true;
} else if (root.getLeft() == null) {
if (depth(root.getRight()) > 1) {
return false;
} else {
return true;
}
} else if (root.getRight() == null) {
if (depth(root.getLeft()) > 1) {
return false;
} else {
return true;
}
} else if (root.getLeft() != null && root.getRight() != null && isBalanced(root.getLeft()) && isBalanced(root.getRight())) {
return true;
} else {
return false;
}
}
}
If this is for your job, I suggest:
Stumbled across this old question while searching for something else. I notice that you never did get a complete answer.
The way to solve this problem is to start by writing a specification for the function you are trying to write.
Specification: A well-formed binary tree is said to be "height-balanced" if (1) it is empty, or (2) its left and right children are height-balanced and the height of the left tree is within 1 of the height of the right tree.
Now that you have the specification, the code is trivial to write. Just follow the specification:
IsHeightBalanced(tree)
return (tree is empty) or
(IsHeightBalanced(tree.left) and
IsHeightBalanced(tree.right) and
abs(Height(tree.left) - Height(tree.right)) <= 1)
Translating that into the programming language of your choice should be trivial.
Bonus exercise: this naive code sketch traverses the tree far too many times when computing the heights. Can you make it more efficient?
Super bonus exercise: suppose the tree is massively unbalanced. Like, a million nodes deep on one side and three deep on the other. Is there a scenario in which this algorithm blows the stack? Can you fix the implementation so that it never blows the stack, even when given a massively unbalanced tree?
UPDATE: Donal Fellows points out in his answer that there are different definitions of 'balanced' that one could choose. For example, one could take a stricter definition of "height balanced", and require that the path length to the nearest empty child is within one of the path to the farthest empty child. My definition is less strict than that, and therefore admits more trees.
One can also be less strict than my definition; one could say that a balanced tree is one in which the maximum path length to an empty tree on each branch differs by no more than two, or three, or some other constant. Or that the maximum path length is some fraction of the minimum path length, like a half or a quarter.
It really doesn't matter usually. The point of any tree-balancing algorithm is to ensure that you do not wind up in the situation where you have a million nodes on one side and three on the other. Donal's definition is fine in theory, but in practice it is a pain coming up with a tree-balancing algorithm that meets that level of strictness. The performance savings usually does not justify the implementation cost. You spend a lot of time doing unnecessary tree rearrangements in order to attain a level of balance that in practice makes little difference. Who cares if sometimes it takes forty branches to get to the farthest leaf in a million-node imperfectly-balanced tree when it could in theory take only twenty in a perfectly balanced tree? The point is that it doesn't ever take a million. Getting from a worst case of a million down to a worst case of forty is usually good enough; you don't have to go all the way to the optimal case.
class Node {
int data;
Node left;
Node right;
// assign variable with constructor
public Node(int data) {
this.data = data;
}
}
public class BinaryTree {
Node root;
// get max depth
public static int maxDepth(Node node) {
if (node == null)
return 0;
return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}
// get min depth
public static int minDepth(Node node) {
if (node == null)
return 0;
return 1 + Math.min(minDepth(node.left), minDepth(node.right));
}
// return max-min<=1 to check if tree balanced
public boolean isBalanced(Node node) {
if (Math.abs(maxDepth(node) - minDepth(node)) <= 1)
return true;
return false;
}
public static void main(String... strings) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
if (tree.isBalanced(tree.root))
System.out.println("Tree is balanced");
else
System.out.println("Tree is not balanced");
}
}
What balanced means depends a bit on the structure at hand. For instance, A B-Tree cannot have nodes more than a certain depth from the root, or less for that matter, all data lives at a fixed depth from the root, but it can be out of balance if the distribution of leaves to leaves-but-one nodes is uneven. Skip-lists Have no notion at all of balance, relying instead on probability to achieve decent performance. Fibonacci trees purposefully fall out of balance, postponing the rebalance to achieve superior asymptotic performance in exchange for occasionally longer updates. AVL and Red-Black trees attach metadata to each node to attain a depth-balance invariant.
All of these structures and more are present in the standard libraries of most common programming systems (except python, RAGE!). Implementing one or two is good programming practice, but its probably not a good use of time to roll your own for production, unless your problem has some peculiar performance need not satisfied by any off-the-shelf collections.
To have a better performance specially on huge trees you can save the height in each node so it is a trade off space Vs performance:
class Node {
Node left;
Node right;
int value;
int height;
}
Example of implementing the addition and same for deletion
void addNode(Node root,int v)
{ int height =0;
while(root != null)
{
// Since we are adding new node so the height
// will increase by one in each node we will pass by
root.height += 1;
height++;
else if(v > root.value){
root = root.left();
}
else{
root = root.right();
}
}
height++;
Node n = new Node(v , height);
root = n;
}
int treeMaxHeight(Node root)
{
return Math.Max(root.left.height,root.right.height);
}
int treeMinHeight(Node root)
{
return Math.Min(root.left.height,root.right.height);
}
Boolean isNodeBlanced(Node root)
{
if (treeMaxHeight(root) - treeMinHeight(root) > 2)
return false;
return true;
}
Boolean isTreeBlanced (Node root)
{
if(root == null || isTreeBalanced(root.left) && isTreeBalanced(root.right) && isNodeBlanced(root))
return true;
return false;
}
Bonus exercise response. The simple solution. Obviously in a real implementation one might wrap this or something to avoid requiring the user to include height in their response.
IsHeightBalanced(tree, out height)
if (tree is empty)
height = 0
return true
balance = IsHeightBalanced(tree.left, heightleft) and IsHeightBalanced(tree.right, heightright)
height = max(heightleft, heightright)+1
return balance and abs(heightleft - heightright) <= 1
This is being made way more complicated than it actually is.
The algorithm is as follows:
Let B = depth of the lowest-level node
If abs(A-B) <= 1, then the tree is balanced
Source: Stackoverflow.com