Balanced Binary Tree

Balanced Binary Tree asks a simple yes-or-no question. Is the tree balanced or not? The interesting part is doing it without re-walking the tree again and again. The interviewer wants to see if you can return two facts from one recursive call.

🎯 The Problem

You get a binary tree. Say if it is height balanced.

The rules:

• A binary tree is a structure where each node has a value and up to two children.
• Height balanced means that for every node, the left height and the right height differ by at most one.
• The rule must hold at every single node, not just the root.
• If even one node has a left side much taller than its right side, the tree is not balanced.

Input:
       1
      / \
     2   3
    / \
   4   5

Output: true

Explanation: At every node the left and right heights differ by at most 1.

Here is the tree. Check each node and you will see no side is more than one taller than the other.

🐢 Approach 1: Top-Down Height Checks (Brute Force)

The idea in one line: at each node, compute both heights and check the rule, then repeat for the children.

The idea:

• Start at the root.
• Compute the height of its left side and its right side.
• If they differ by more than one, answer no.
• Otherwise repeat the same check for the left child and the right child.

How it works:

• To check one node, you measure heights, which walks the whole subtree.
• Then you move to a child and do it again.

Why it is weak:

• The same heights get measured over and over.
• On a long thin tree this climbs to about O(n²) time.
• It is pure repeated work.

Here is the top-down height-check code:

def is_balanced(root):
    def height(node):
        if not node: return 0
        return 1 + max(height(node.left), height(node.right))
    if not root: return True
    return abs(height(root.left) - height(root.right)) <= 1 and is_balanced(root.left) and is_balanced(root.right)

⚡ Approach 2: Bottom-Up In One Pass (Best)

The idea in one line: solve the children first and let one return value carry both the height and a broken flag.

The idea:

• Work from the bottom up, not the top down.
• Bottom up means solve the children first, then use their answers for the parent.
• So you never re-walk a subtree.

How it works:

• One recursive function returns the height of a node.
• But it also carries a signal. A special value like -1 means “broken below.”
• So the return value means two things: the normal height, or the broken flag.
• At each node, get the left result and the right result.
• If either is -1, pass -1 up right away.
• If the two heights differ by more than one, this node is unbalanced, so return -1.
• Otherwise return the real height to the parent.
• If the top call is not -1, the tree is balanced.

Why it is fast:

• Each node is touched once.
• That is O(n). Much faster than the top-down way.

The diagram below shows heights flowing up from the leaves, with -1 meaning a broken subtree was found.

Steps to Solve

1. Write a recursive check(node) that returns the height, or -1 if unbalanced.
2. If the node is empty, return a height of 0.
3. Get the left result. If it is -1, return -1.
4. Get the right result. If it is -1, return -1.
5. If the two heights differ by more than 1, return -1.
6. Otherwise return the larger height plus 1.
7. The tree is balanced if the top call does not return -1.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node *left;
    struct Node *right;
} Node;

Node *newNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->val = val;
    n->left = NULL;
    n->right = NULL;
    return n;
}

int absDiff(int a, int b) { return a > b ? a - b : b - a; }
int maxInt(int a, int b) { return a > b ? a : b; }

// returns height, or -1 if any subtree below is unbalanced
int check(Node *node) {
    if (node == NULL) return 0;
    int lh = check(node->left);
    if (lh == -1) return -1;                 // broken below on the left
    int rh = check(node->right);
    if (rh == -1) return -1;                 // broken below on the right
    if (absDiff(lh, rh) > 1) return -1;      // unbalanced here
    return maxInt(lh, rh) + 1;               // height for the parent
}

int isBalanced(Node *root) {
    return check(root) != -1;
}

int main(void) {
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("%s\n", isBalanced(root) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

struct Node {
    int val;
    Node *left;
    Node *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

// returns height, or -1 if unbalanced
int check(Node *node) {
    if (node == nullptr) return 0;
    int lh = check(node->left);
    if (lh == -1) return -1;
    int rh = check(node->right);
    if (rh == -1) return -1;
    if (abs(lh - rh) > 1) return -1;   // unbalanced here
    return max(lh, rh) + 1;            // height for the parent
}

bool isBalanced(Node *root) {
    return check(root) != -1;
}

int main() {
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    cout << (isBalanced(root) ? "true" : "false") << endl;
    return 0;
}

true

public class Balanced {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    // returns height, or -1 if unbalanced
    static int check(Node node) {
        if (node == null) return 0;
        int lh = check(node.left);
        if (lh == -1) return -1;
        int rh = check(node.right);
        if (rh == -1) return -1;
        if (Math.abs(lh - rh) > 1) return -1;  // unbalanced here
        return Math.max(lh, rh) + 1;           // height for the parent
    }

    static boolean isBalanced(Node root) {
        return check(root) != -1;
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        System.out.println(isBalanced(root));
    }
}

true

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def is_balanced(root):
    def check(node):
        if node is None:
            return 0                   # empty: height 0
        lh = check(node.left)          # left height or -1
        if lh == -1:
            return -1                  # broken below on the left
        rh = check(node.right)         # right height or -1
        if rh == -1:
            return -1                  # broken below on the right
        if abs(lh - rh) > 1:
            return -1                  # unbalanced at this node
        return max(lh, rh) + 1         # height for the parent

    return check(root) != -1


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(is_balanced(root))

True

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function isBalanced(root) {
  function check(node) {
    if (node === null) return 0;           // empty: height 0
    const lh = check(node.left);
    if (lh === -1) return -1;              // broken on the left
    const rh = check(node.right);
    if (rh === -1) return -1;              // broken on the right
    if (Math.abs(lh - rh) > 1) return -1;  // unbalanced here
    return Math.max(lh, rh) + 1;           // height for the parent
  }

  return check(root) !== -1;
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

console.log(isBalanced(root));

true

Let us walk through the Python version line by line so the signal trick is clear.

The inner check starts with if node is None: return 0. An empty spot has height 0. This is the base case where the recursion stops.

Next, lh = check(node.left) gets the left side. Then if lh == -1: return -1. Here is the key. The left side already reported it is broken. So this node is broken too. We do not waste time looking further. We send -1 straight up.

Then rh = check(node.right) and if rh == -1: return -1 do the same for the right side. If the right side is broken, we stop and pass the broken flag up.

Then if abs(lh - rh) > 1: return -1. Both sides came back as real heights. But if they differ by more than one, this node itself breaks the balance rule. So we return -1.

Finally return max(lh, rh) + 1. This node is fine and both sides are fine. So we hand the parent the real height: the taller side plus one.

The outer line return check(root) != -1 turns the height-or-flag result into a clean true or false.

⏱️ Time and Space Complexity

The top-down way recomputes heights, so it is O(n²). The bottom-up way visits each node once and does fixed work, so it is O(n). The space is the recursion depth, which is O(h) where h is the height of the tree.

🧩 Key Takeaways

• ✅ Balanced means every node’s left and right heights differ by at most one.
• ✅ The rule must hold at every node, not just at the root.
• ✅ Work bottom up so you compute each height only once.
• ✅ Use a special value like -1 to carry “unbalanced” up the recursion.
• ✅ The bottom-up version is O(n), far faster than the top-down O(n²).

🚀 What’s Next?

• Diameter of Binary Tree
• Same Tree