How to determine if binary tree is balanced?

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.

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.

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, out heightleft) and IsHeightBalanced(tree.right, out heightright)
    height = max(heightleft, heightright)+1
    return balance and abs(heightleft - heightright) <= 1     

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.

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.

If this is for your job, I suggest:

1. do not reinvent the wheel and
2. use/buy COTS instead of fiddling with bits.
3. Save your time/energy for solving business problems.

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.

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

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.

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 );
}

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");
    }
}

Recursively check if each subtree is balanced or not. Recursion means, you ask something to subtree and subtree will return a response. You keep asking till you hit the base case. in tree questions base case is when you hit the leaf node.

In this case, we ask 2 questions to a subtree:

1- Are you balanced?

2- What is your height?

So recursive function will return 2 answers, and I keep those answers in the array.

This is python code:

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(root):
            # leaf node is balanced
            if not root:
                # we carry the height of each subtree
                return [True,0]
            # with recursion, we start from bottom, so we do not have repetitive work
            left,right=dfs(root.left),dfs(root.right)
            # if any of the subtree return false, then we know entire tree is not balanced
            balanced=left[0] and right[0] and abs(left[1]-right[1])<=1
            # 1+max(left[1],right[1]) is the height of the each subtree. 1 is the root of the subtree
            return [balanced,1+max(left[1],right[1])]
        return dfs(root)[0]

this is javascript code:

var isBalanced = function(root) {
 function dfs(root){
     if(!root){
         return [true,0]
     }
     
     const left=dfs(root.left)
     const right=dfs(root.right)
     const balanced=left[0] && right[0] && Math.abs(left[1]-right[1])<=1
     return [balanced,1+Math.max(left[1],right[1])]
 }
    return dfs(root)[0]
};

a height-balanced binary tree is a binary tree in which the depth of the two subtrees of each node does not differ by more than one

here's the tree node

public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}

    public bool IsBalanced(TreeNode root)
    {
        if(root == null)
        {
            return true;
        }
        
        var left = Depth(root.Left);
        var right = Depth(root.Right);
        
        if(Math.Abs(left - right) > 1)
        {
            return false;
        }
        
        return IsBalanced(root.Left) && IsBalanced(root.Right);
    }
    
    private int Depth(TreeNode node)
    {
        if(node == null)
        {
            return 0;
        }
        return Math.Max(Depth(node.Left), Depth(node.Right)) + 1;
    }

you can try to practice here

Wouldn't this work?

return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );

Any unbalanced tree would always fail this.