The challenge
Check whether every node has left and right subtree heights differing by at most one.
Balance must hold at every node, not only at the root. Empty trees are balanced.
Example
Balanced example: true. The three-node right chain: false.
Use the walkthrough below to inspect the input and each state change.
See Balanced tree, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
Return a height when valid and −1 as soon as any subtree is unbalanced.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def is_balanced(root):
def check(node):
if node is None:
return 0
left = check(node.left)
if left == -1:
return -1
right = check(node.right)
if right == -1 or abs(left - right) > 1:
return -1
return 1 + max(left, right)
return check(root) != -1
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
bool is_balanced(Node* root) {
function<int(Node*)> check = [&](Node* node) -> int {
if (!node) return 0;
int left = check(node->left);
if (left == -1) return -1;
int right = check(node->right);
if (right == -1 || abs(left - right) > 1) return -1;
return 1 + max(left, right);
};
return check(root) != -1;
}