Balanced Tree

A binary tree is height-balanced when every node's left and right subtree heights differ by at most 1. The every node part matters. It is not enough for the root to look balanced if a deeper subtree is badly skewed.

Using the leaf-height-zero convention, a missing child has height -1 inside calculations. A leaf is balanced because both child heights are -1. A node with one leaf child and one missing child is also balanced because the difference is 1.

Operations that follow a root-to-leaf path are bounded by height. In a balanced tree with n nodes, height is O(log n), so BST search, insertion, deletion, and many navigation tasks are logarithmic. In a skewed tree, height can become O(n), and those same operations become linear.

This is why the phrase O(h) is precise and the phrase O(log n) needs a balance assumption. Balance is the structural reason logarithmic performance is possible.

Ordinary binary search trees do not automatically stay balanced. If values arrive in sorted order, the tree can lean into a chain. Self-balancing BSTs such as AVL trees and red-black trees add rotation rules after insertions and deletions so height remains logarithmic.

You usually do not implement those rotations in a basic tree interview unless the problem asks for it. Still, knowing the purpose matters: rotations preserve the BST ordering invariant while changing shape to reduce height.

To check whether a tree is balanced, compute heights bottom-up. For each node, ask the left and right subtrees for their heights. If either subtree is already unbalanced, propagate failure. Otherwise, compare the two heights and return the current height.

This combines two tasks in one postorder traversal: validate the balance rule and compute the height needed by the parent. The common efficient pattern returns a sentinel such as -2 or a pair containing height and balance status, avoiding repeated height recomputation.