Tree Properties

Height, diameter, balance — the measurements that describe a tree and gate whether it stays fast.

The problem

Two teams store the same 1,000 users in a binary search tree. One team's lookups return instantly; the other's crawl. Same data, same code, wildly different speed. The difference isn't the algorithm — it's the shape of their trees.

A tree's performance lives in a handful of measurements: how tall it is, how wide, how lopsided. Get those numbers wrong and a structure that promised O(log n) silently delivers O(n). Before you can keep a tree fast, you have to be able to measure it.

A first attempt

The measurements feel independent, so you write a separate walk for each: one function to find the height, another to find the diameter, another to check balance. The balance check calls the height function at every node to compare left and right subtree heights.

That last combination bites. Computing height is O(n). Calling it at every one of the n nodes to check balance makes the whole thing O(n²) — and on a big skewed tree it's painfully slow. You're recomputing the same subtree heights over and over, throwing the answer away each time.

The insight

Every one of these measurements is a post-order computation: a node's answer is a small function of the answers already computed for its two children. Height is 1 + max(left height, right height). So if each recursive call returns the height as it unwinds, a parent gets its children's heights for free — no recomputation.

Better still, you can compute several properties in that single upward pass. Return height from the recursion, and while you're at it, use leftHeight + rightHeight at each node to track the widest path — the diameter — with a shared variable. One O(n) traversal, many answers.

How it works

Height in one post-order pass

Define height as edges on the longest downward path (an empty tree is −1, a leaf is 0; some texts count nodes and start at 1 — pick one and be consistent). Recurse: return 1 + max(left, right). Each node sees its children's heights already computed.

        A            height(A) = 1 + max(2, 0) = 3 (edges)
       / \
      B   C          height(B) = 2, height(C) = 0
     /
    D
   /
  E

Diameter piggybacks on height

The diameter is the longest path between any two nodes, measured in edges. At each node the longest path through it is leftHeight + rightHeight. Keep a running maximum of that value across all nodes while the height recursion runs — one pass, both answers.

Balance is a height check with an early exit

A tree is height-balanced if, at every node, the left and right subtree heights differ by at most 1. Reuse the height recursion, but if any node is unbalanced, propagate a sentinel (like −∞ or a boolean flag) up so the whole call short-circuits — still O(n).

Why balance matters

A balanced tree of n nodes has height ≈ log₂ n, so search, insert, and delete stay O(log n). Let it grow lopsided and height climbs toward n, dragging every operation down to O(n). Self-balancing trees (AVL, red-black) exist precisely to keep this number in check.

The code

def height(node):
    if node is None:
        return -1                       # empty tree: -1 edge
    return 1 + max(height(node.left), height(node.right))

def diameter(root):
    best = 0
    def depth(node):
        nonlocal best
        if node is None:
            return -1
        l = depth(node.left)
        r = depth(node.right)
        best = max(best, (l + 1) + (r + 1))   # edges through this node
        return 1 + max(l, r)
    depth(root)
    return best

def is_balanced(root):
    def check(node):                    # returns height, or -2 if unbalanced
        if node is None:
            return -1
        l = check(node.left)
        if l == -2: return -2
        r = check(node.right)
        if r == -2: return -2
        if abs(l - r) > 1: return -2
        return 1 + max(l, r)
    return check(root) != -2

function height(node: TreeNode | null): number {
  if (node === null) return -1;
  return 1 + Math.max(height(node.left), height(node.right));
}

function diameter(root: TreeNode | null): number {
  let best = 0;
  function depth(node: TreeNode | null): number {
    if (node === null) return -1;
    const l = depth(node.left);
    const r = depth(node.right);
    best = Math.max(best, l + 1 + (r + 1)); // edges through node
    return 1 + Math.max(l, r);
  }
  depth(root);
  return best;
}

function isBalanced(root: TreeNode | null): boolean {
  function check(node: TreeNode | null): number { // -2 = unbalanced
    if (node === null) return -1;
    const l = check(node.left);
    if (l === -2) return -2;
    const r = check(node.right);
    if (r === -2) return -2;
    if (Math.abs(l - r) > 1) return -2;
    return 1 + Math.max(l, r);
  }
  return check(root) !== -2;
}

class Properties {
    static int height(TreeNode node) {
        if (node == null) return -1;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    static int best;
    static int diameter(TreeNode root) {
        best = 0;
        depth(root);
        return best;
    }
    static int depth(TreeNode node) {
        if (node == null) return -1;
        int l = depth(node.left);
        int r = depth(node.right);
        best = Math.max(best, (l + 1) + (r + 1)); // edges through node
        return 1 + Math.max(l, r);
    }

    static boolean isBalanced(TreeNode root) {
        return check(root) != -2;
    }
    static int check(TreeNode node) {   // -2 = unbalanced
        if (node == null) return -1;
        int l = check(node.left);
        if (l == -2) return -2;
        int r = check(node.right);
        if (r == -2) return -2;
        if (Math.abs(l - r) > 1) return -2;
        return 1 + Math.max(l, r);
    }
}

#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *left, *right;
} Node;

int max(int a, int b) { return a > b ? a : b; }

int height(Node *node) {
    if (node == NULL) return -1;
    return 1 + max(height(node->left), height(node->right));
}

int best;
int depth(Node *node) {
    if (node == NULL) return -1;
    int l = depth(node->left);
    int r = depth(node->right);
    if ((l + 1) + (r + 1) > best) best = (l + 1) + (r + 1);
    return 1 + max(l, r);
}
int diameter(Node *root) {
    best = 0;
    depth(root);
    return best;
}

/* returns height, or -2 if any subtree is unbalanced */
int check(Node *node) {
    if (node == NULL) return -1;
    int l = check(node->left);
    if (l == -2) return -2;
    int r = check(node->right);
    if (r == -2) return -2;
    if (abs(l - r) > 1) return -2;
    return 1 + max(l, r);
}
int isBalanced(Node *root) { return check(root) != -2; }

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

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

int height(Node *node) {
    if (node == nullptr) return -1;
    return 1 + max(height(node->left), height(node->right));
}

int best;
int depth(Node *node) {
    if (node == nullptr) return -1;
    int l = depth(node->left);
    int r = depth(node->right);
    best = max(best, (l + 1) + (r + 1));   // edges through node
    return 1 + max(l, r);
}
int diameter(Node *root) {
    best = 0;
    depth(root);
    return best;
}

int check(Node *node) {                     // -2 = unbalanced
    if (node == nullptr) return -1;
    int l = check(node->left);
    if (l == -2) return -2;
    int r = check(node->right);
    if (r == -2) return -2;
    if (abs(l - r) > 1) return -2;
    return 1 + max(l, r);
}
bool isBalanced(Node *root) { return check(root) != -2; }

Complexity

Property	Naive	With shared post-order pass
Height	O(n)	O(n)
Diameter	O(n²) (height per node)	O(n)
Balanced check	O(n²)	O(n)

Space for all of them is O(h) for the recursion stack. The win is turning the O(n²) "call height at every node" pattern into a single bottom-up O(n) traversal.

When to use it

Compute properties bottom-up, and watch your height convention

Whenever a tree property depends on subtree answers — height, diameter, sum, count, balance, subtree size — compute it in one post-order pass and return the child answer up the stack instead of recomputing it. The classic trap is diameter and balance done with a nested height call, which is O(n²); fold them into the height recursion for O(n). Pick one height convention (edges vs. nodes) and stick to it across your whole codebase, because off-by-one errors here silently corrupt balance checks.

Practice

Recap

A tree's speed is governed by its shape — height, width, and balance are the numbers that describe it.
Height, diameter, size, and balance are all post-order computations: return a child's answer up the stack instead of recomputing it.
Folding diameter and balance into the height recursion turns an O(n²) mistake into a clean O(n) pass.

Tree Properties

The problem

A first attempt

The insight

How it works

Height in one post-order pass

Diameter piggybacks on height

Balance is a height check with an early exit

Why balance matters

The code

Complexity

When to use it

Practice

Recap

Binary Trees

Tree Traversals

Ancestors & Paths

On this page

Tree Properties

Why is the naive diameter algorithm O(n²), and how does the one-pass version fix it?

Is the diameter path always required to pass through the root? Give an example.

A balanced binary tree has n nodes. What is its height, and why does that guarantee fast operations?

Binary Trees

Tree Traversals

Ancestors & Paths

On this page