Abstract / Summary

Determine if a binary tree is height balanced so that the depth difference between left and right subtrees of every node does not exceed one.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 59% (4+ million submissions).

Typical patterns to solve this problem:

• Binary Tree
• Depth First Search
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single public method isBalanced. The method determines whether a binary tree, represented by TreeNode objects, satisfies the height-balanced property: for every node, the heights of its left and right subtrees differ by no more than one. The algorithm employs a depth-first recursion that simultaneously computes subtree heights and detects imbalance, returning a Boolean result.

Key Steps

Sentinel Value Definition

A special floating-point value, failed, is created to signal that an imbalance has been discovered in any part of the tree.

failed = float("inf")

Recursive Height Computation

A nested helper function deeper performs a post-order traversal. For a None node it returns a height of zero, establishing the base case for leaf children.

def deeper(node):
    if not node:
        return 0

Left and Right Subtree Evaluation

The function recursively obtains the heights of the left and right children.

l = deeper(node.left)
r = deeper(node.right)

Imbalance Detection and Propagation

If either child already reported an imbalance (l == failed or r == failed) or the current node’s subtrees differ in height by more than one, the function returns the sentinel failed. This return value propagates upward, preventing further unnecessary height calculations.

if l == failed or r == failed or abs(l - r) > 1:
    return float("inf")

Height Aggregation for Balanced Nodes

When the current node is balanced, its height is one plus the larger of its children’s heights.

else:
    return 1 + max(l, r)

Final Result Determination

The public method invokes deeper on the root and checks whether the sentinel was ever returned. A non-sentinel result indicates the entire tree is balanced.

return deeper(root) != failed

Edge Cases Handled

The algorithm gracefully manages an empty tree because the base case returns zero for a None root, and the final comparison against failed yields True.

When a subtree is already known to be unbalanced, the sentinel value is immediately returned without further descent, ensuring that deeper recursive calls do not waste cycles on already invalid portions of the structure.

The use of abs(l - r) > 1 captures the precise condition for imbalance at each node, covering scenarios where one side is significantly deeper than the other, including cases where one child is missing (None) and the other is a deep chain.

Because the sentinel is a floating-point infinity, it cannot be confused with any legitimate integer height, guaranteeing correct detection even for very tall trees.

Performance Optimizations

The most notable optimization is the early-exit mechanism implemented via the sentinel failed. As soon as an imbalance is detected at any node, the recursion stops propagating real height values and instead returns the sentinel upward. This prevents the algorithm from traversing the remainder of the tree once the answer is known, reducing the number of recursive calls in unbalanced cases.

The algorithm also avoids separate passes for height calculation and balance checking. By merging both concerns into a single post-order traversal, it eliminates redundant work that a naïve two-pass approach would incur.

Since each node is visited at most once and the height information is computed in constant time per node, the overall execution follows a linear pattern relative to the number of nodes, with minimal overhead from the sentinel checks.

The use of local variables (l, r) and direct arithmetic (abs, max) keeps the inner loop tight, contributing to fast execution on typical Python interpreters.

Imagine a giant family tree where every person has at most two children dangling below them. This code is a clever helper that explores the tree from the top all the way down to the bottom to see if it looks neat and tidy.

First, the helper looks at an empty spot and decides that it has a height of zero. If it finds a person, it quickly runs over to check the left side and the right side to see how deep they go. It keeps track of those heights while it travels back up the branches.

As it climbs back up, it compares the height of the left side and the right side. If one side is much taller than the other, it marks the tree as broken by setting a special signal. If the sides are close enough in height, it adds one to the taller side to show the new height of that branch. By the time it finishes checking every single branch, it concludes whether the whole tree is balanced or if it has become too lopsided.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java						TS
	WalkCCC	C++	Python			Java
	leetcode.ca	C++	Python	Rust	JS	Java		Go				TS
	LeetcodeHelp	C++	Python			Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python			Java
github	aylei			Rust
	begeekmyfriend								C
	BigEggStudy						C#
	black-shadows		Python
	bujosa			Rust
	chandansgowda		Python
	charles-wangkai					Java
	chenyanzhe	C++
	DimitrisJim				JS
	everthis				JS
	fartem									Ruby
	fengvyi	C++
	gaosq0604		Python
	halfrost							Go
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	lennylxx								C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	muhammadfarhankt							Go
	qiyuangong		Python
	ruoru			Rust
	shreymehul						C#
	sonugiri1043	C++
	suxrobGM						C#
	varunu28					Java
	vthwang					Java
	wisdompeak	C++
	withaarzoo	C++
	XiaotaoGuo	C++
	yuanliu666										Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	Python, Python
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	JavaScript
everthis	JavaScript
fartem	Ruby
fengvyi	C++
gaosq0604	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
muhammadfarhankt	Go
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vthwang	Java
wisdompeak	C++
withaarzoo	C++
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality