Abstract / Summary

Find the longest path in a binary tree where each step moves to a child at a different level than the previous step.

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 66% (300k+ submissions).

Typical patterns to solve this problem:

• Binary Tree
• Depth First Search
• Dynamic Programming
• 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 method longestZigZag that computes the length of the longest ZigZag path in a binary tree. A ZigZag path is a sequence of nodes where each step alternates between left and right child directions. The algorithm relies on a depth-first recursion combined with memoization to avoid redundant calculations, and it maintains a global best variable that records the maximum length discovered during traversal.

Core Logic

At the entry point, the method initializes a variable best to zero. This variable is declared in the outer scope of the nested function so that updates made inside the recursion are reflected throughout the execution.

best = 0

A nested function deeper is defined and decorated with @cache. The decorator supplies memoization, ensuring that each unique combination of a node and a direction flag (goLeft) is evaluated at most once. The function returns the length of the ZigZag path that starts at the given node and proceeds in the direction indicated by goLeft.

@cache
def deeper(node, goLeft):
    if not node:
        return 0
    ...

The method invokes deeper twice from the root-once assuming the first move should go left and once assuming it should go right. The final result is the value stored in best.

deeper(root, True)
deeper(root, False)
return best

Recursive Exploration

Inside deeper, the base case checks for a null node and returns zero, representing the absence of further steps. For a non-null node, the function recursively explores both children, but it flips the expected direction for each recursive call. The flip is achieved by applying the logical negation operator to goLeft.

l = deeper(node.left,  not goLeft)
r = deeper(node.right, not goLeft)

If the current call expects a left move (goLeft is true), the length contributed by the left subtree (l) is considered. The global best is updated with the maximum of its current value and l. The function then returns l + 1, accounting for the current node as part of the path. Conversely, when a right move is expected, the right subtree length (r) drives the update and return value.

if goLeft:
    best = max(best, l)
    return l + 1
else:
    best = max(best, r)
    return r + 1

This pattern guarantees that each recursive step respects the alternating direction constraint inherent to a ZigZag path.

State Management

The use of nonlocal best inside deeper allows the nested function to modify the best variable defined in the enclosing scope. This design eliminates the need to pass an accumulator through recursive arguments and keeps the update logic localized to the point where a candidate length is computed.

nonlocal best

The memoization provided by @cache stores results keyed by the tuple (node, goLeft). Because a node can be visited with either a left-expected or right-expected direction, the cache distinguishes these two states, preventing recomputation while preserving correctness.

Edge Cases Handled

When the input tree is empty (root is None), the initial calls to deeper immediately hit the base case, returning zero without altering best. Consequently, the method returns zero, correctly indicating that no ZigZag path exists.

If the tree consists of a single node, the recursion still proceeds to the base case for both children, each yielding zero. The best variable remains zero because a ZigZag path requires at least one directional move. The method therefore returns zero, matching the definition that a solitary node does not form a ZigZag.

For highly unbalanced trees where all nodes lie on one side, the recursion explores the existing branch while the opposite child is always None. The base case quickly terminates those dead ends, and the alternating direction logic ensures that the path length does not erroneously count consecutive moves in the same direction.

When the tree contains multiple ZigZag candidates of varying lengths, the global best variable is updated each time a longer candidate is discovered. Because the updates happen after each recursive return, the algorithm captures the maximum length regardless of where the longest ZigZag originates in the tree.

Performance Optimizations

The primary optimization stems from the @cache decorator. By caching the result of each (node, goLeft) pair, the algorithm avoids exponential blow-up that would otherwise arise from exploring overlapping subproblems. Each node is processed at most twice-once for a left-expected move and once for a right-expected move-resulting in a linear number of recursive evaluations relative to the number of nodes.

The early return for null nodes eliminates unnecessary work for leaf children, ensuring that the recursion terminates promptly at the tree boundaries. The use of a single mutable best variable avoids the overhead of constructing and merging auxiliary data structures during the traversal.

Overall, the combination of memoization, concise base-case handling, and in-place state updates yields an implementation that scales efficiently with the size of the input tree while preserving clarity in its logical flow.

Imagine a giant tree made of branches that fork off into left paths and right paths. This code is like a little explorer wandering through the tree to find the longest path that zigs and zags.

Whenever the explorer lands on a branch, it asks a question about which direction to take next. If the explorer just went to the left, it has to turn and go to the right to keep the zigzag going. If it just went to the right, it has to turn and go left.

The explorer keeps track of how many steps it has taken in a row without making a mistake. Every time it takes a step, it tells itself what its current streak is. If at any point it finds a new path that is longer than the best one it has seen before, it remembers that new streak as the best one.

It starts the journey twice from the very top of the tree, once trying to head left first and once trying to head right first. By doing this, the code finds the longest possible zigzag path hidden anywhere inside the branches of the tree.

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++	Java	Python				TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python			Go
	Progiez	C++	Java	Python
github	begeekmyfriend					C
	black-shadows	C++
	charles-wangkai		Java
	fsq	C++
	JoshCrozier				JS
	lkwq007			Python
	lzl124631x	C++
	varunu28		Java
	vthwang		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
begeekmyfriend	C
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
lzl124631x	C++
varunu28	Java
vthwang	Java

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