Abstract / Summary

Check if a binary tree is even-odd by verifying nodes at even levels have only odd children and odd levels have only even children.

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 67% (200k+ submissions).

Typical patterns to solve this problem:

• Binary Tree
• Breadth 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 isEvenOddTree. The method determines whether a binary tree satisfies the “even-odd” constraints: nodes on even-indexed levels must contain odd values that strictly increase from left to right, while nodes on odd-indexed levels must contain even values that strictly decrease from left to right. The algorithm traverses the tree depth-first, maintaining per-level state in a dictionary called prev. Each recursive call validates the current node against the level’s parity rules and the ordering constraints established by previously visited nodes on the same level.

Core Logic

Entry Point

def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
    prev = {}
    return deeper(root, 0)

The method initializes an empty dictionary prev that will store the most recent value seen at each depth. It then invokes the nested helper deeper starting at the root with a height of 0.

Recursive Helper

def deeper(node, height):
    if not node:
        return True

The helper receives a node and its depth (height). An immediate return of True for a None node treats absent children as trivially satisfying the constraints, allowing the recursion to unwind cleanly.

Depth-First Exploration

if not deeper(node.left,  height + 1) or \
   not deeper(node.right, height + 1):
    return False

The function first recurses into the left and right subtrees, incrementing the depth. The logical or short-circuits: if either subtree violates the rules, the entire call returns False. This ordering ensures that all deeper nodes are examined before the current node’s value is validated, which is essential for the later ordering checks.

Parity Validation

if height % 2 == node.val % 2:
    return False

The parity condition is enforced by comparing the parity of the depth with the parity of the node’s value. For even depths (height % 2 == 0), the node value must be odd (node.val % 2 == 1), and vice versa. A mismatch leads to an immediate failure.

Level-Order Monotonicity

if height % 2 == 0:
    if prev.get(height, float("-inf")) >= node.val:
        return False
else:
    if prev.get(height, float("+inf")) <= node.val:
        return False

For even levels, the algorithm expects strictly increasing values. It retrieves the previously recorded value for the current depth from prev, defaulting to negative infinity so that the first node on the level always passes. If the stored value is not less than the current node’s value, the monotonicity rule is broken.

For odd levels, the expectation is strictly decreasing values. The default is positive infinity, guaranteeing that the first node on an odd level satisfies the decreasing condition. If the stored value is not greater than the current node’s value, the check fails.

State Update

prev[height] = node.val
return True

After all validations succeed, the current node’s value becomes the new reference for subsequent nodes on the same level. The function then returns True to indicate that the subtree rooted at this node conforms to the even-odd tree definition.

Edge Cases Handled

The recursion gracefully handles an empty tree because the initial call receives root. If root is None, the helper returns True immediately, treating an empty structure as a valid even-odd tree.

When a level contains only a single node, the default values (-inf for even levels, +inf for odd levels) guarantee that the ordering check passes without requiring special-case logic.

The code also correctly processes trees that are highly unbalanced. Since the depth-first traversal visits every node regardless of shape, nodes at any depth are validated against the appropriate parity and ordering constraints.

Performance Optimizations

The algorithm uses a single dictionary prev to store the most recent value per depth, avoiding the need for auxiliary data structures such as queues or lists that would be required for a breadth-first approach. This in-place update reduces memory overhead.

By performing the depth-first recursion before the current node’s validation, the implementation ensures that the prev dictionary always contains the latest value from the leftmost node at a given depth. This ordering eliminates the need for additional bookkeeping to track the traversal order within a level.

The use of dict.get with sentinel values (float("-inf") and float("+inf")) provides constant-time retrieval and default handling, streamlining the monotonicity checks without extra conditional branches.

Overall, the solution achieves a single pass over the tree, evaluating each node exactly once while maintaining only O(h) auxiliary state, where h is the height of the tree. This design yields efficient execution for both shallow and deep trees.

Imagine a big family tree made of numbers. This code is like a little helper walking through the tree to check if everything is in the right spot based on a special secret rule.

The helper starts at the very top of the tree and begins a journey down every branch. As it visits each spot, it keeps track of how deep it has gone. Because the tree is quite tall, the helper remembers the numbers it has already seen at each level by using a handy list.

When the helper stands on a number, it looks at two things. First, it checks the level deepness to see if the number is odd or even, because the rules change depending on whether the level is even or odd. If the number does not follow the correct pattern for that level, the helper realizes something is wrong.

Second, the helper looks at the number that was just visited at that same level. If it is an even level, the numbers must keep getting bigger as the helper moves along. If it is an odd level, the numbers must keep getting smaller. If the numbers do not grow or shrink in the right way, the helper knows the tree is not quite right.

The helper travels through every single leaf and branch of the tree this way. If every group of numbers follows the rules perfectly without any mistakes, then the job is done.

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		Java		Go
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem					Ruby
	fsq	C++
	halfrost						Go
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007		Python
	MacJim	C++
	suxrobGM							C#
	trung-hn		Python
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
MacJim	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

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