In previous articles, we covered the fundamental approach to solving binary tree problems: the subproblem method, along with some basic techniques (Subproblem Decomposition in Binary Trees and Global Variables in Binary Tree Traversal). However, the examples in those articles were limited to relatively simple problems. If you jump straight to harder problems right after learning the basics, you’ll likely feel lost. This article teaches you a “three-step” method that lets you untangle even complex binary tree problems and derive a solution step by step!
The two problems we’ll cover have consecutive problem numbers and both come from LeetCode Biweekly Contest 21:
LeetCode Biweekly Contest 21
As you can see, these two problems are the last two in the contest, with difficulty levels of Medium and Hard respectively. Looks challenging, right? Don’t worry — follow along with my explanation, and you’ll be able to solve binary tree problems at this difficulty level too!
The “Three-Step” Method for Binary Tree Problems
Most binary tree problems can be solved using the subproblem method. The subproblem method delegates the task to the left and right subtrees for recursive computation, then aggregates all results at the root node.
However, in harder binary tree problems, the subproblems aren’t always easy to identify. While analyzing one subproblem, you might discover even more subproblems, and the relationships between them can be tangled… When facing this situation, we need a systematic approach. That approach is the “Three-Step” Method for binary tree problems that I’ll teach you today.
The three steps are:
Step 1 [Decompose Subproblems]: Break the problem down into subproblems as much as possible. Complex problems likely have more than one subproblem. Keep decomposing until you can’t decompose any further. The goal of this step is to identify all subproblems.
Step 2 [Extract Global Variables]: If the desired result involves all subtrees, consider using a global variable. If the result to return is the maximum value across all subtrees, or the sum across all subtrees, you can continuously update a variable during traversal to keep the code cleaner.
Step 3 [Write the Recursive Function]: The recursive function should return as many values as there are subproblems. Many problems are tricky precisely because the recursive function needs to return multiple values, turning the code into a tangled mess. But if you’re clear that each return value corresponds to a subproblem, it won’t be so confusing.
Now let’s see how to apply the three-step method to these two example problems.
Longest ZigZag Path in a Binary Tree
Problem description:
Given a binary tree, a zigzag path is a top-to-bottom path where left edges (edges going to the left child) and right edges (edges going to the right child) alternate. The length of a zigzag path is defined as the number of edges in the path, or the number of nodes minus one. Return the length of the longest zigzag path in the given binary tree.
Problem example
Let’s directly apply the three-step approach:
Step 1: Decompose Subproblems
From the problem example, we can see that the longest zigzag path in a binary tree doesn’t necessarily pass through the root. So the first subproblem decomposition that comes to mind is:
We can see that the subproblem “longest zigzag path” is delegated to subtrees, but a new subproblem emerges: “longest zigzag root path” (here root path means a path starting from the root node). We need to continue decomposing this subproblem.
After a zigzag root path leaves the root, if the first step goes left, the next step in the left subtree must go right; if the first step goes right, the next step in the right subtree must go left. To distinguish these two cases, let’s split zigzag paths into left-zig paths (paths that start by going left) and right-zig paths (paths that start by going right), as shown below.
Splitting zigzag paths into left-zig and right-zig paths
This way, the subproblem “longest zigzag root path” can be decomposed as:
An important note: the left-zig and right-zig paths we need must start from the root node. This is because only paths starting from the root can connect with the path coming from the parent node. This gives us two more subproblems: “longest left-zig root path” and “longest right-zig root path.”
Additionally, “longest zigzag root path” can actually be expressed in terms of “longest left-zig root path” and “longest right-zig root path,” so the formula above can be rewritten as:
OK, now we have the complete subproblem recurrence formulas. Let’s write out all the formulas together:
After fully decomposing the subproblems, we can see exactly how many subproblems exist. The formulas above use colors to clearly mark them — there are three subproblems in total:
Longest zigzag path
Longest left-zig root path
Longest right-zig root path
Step 2: Extract Global Variables
The three subproblems we identified are: (1) “longest zigzag path,” (2) “longest left-zig root path,” and (3) “longest right-zig root path.” The first subproblem is the result the problem asks for — we call it the primary subproblem. The other two are helpers — we call them auxiliary subproblems.
In this step, we determine whether the primary subproblem should be extracted into a global variable. Extracting global variables during binary tree traversal is a very common technique, which we covered in detail in the previous article. If you’re unfamiliar with this technique, you can review the previous article: Binary Tree Diameter: Global Variables in Binary Tree Traversal.
Generally, a subproblem suitable for extraction as a global variable has this characteristic: the final result the problem asks for is either the maximum across all subtrees’ subproblems, or the sum across all subtrees’ subproblems — in short, it involves subproblems across all subtrees, not just the subproblem at the root node.
This problem is a classic example: we need to find the longest zigzag path in the entire binary tree, and this path doesn’t necessarily pass through the root. So the root delegates the task to its left and right subtrees, which in turn delegate to their own subtrees… The computed results then need to be aggregated back up layer by layer. Passing and aggregating these results through the recursive function’s return values would make the code verbose. Storing the result in a global variable makes things much simpler.
int res; // Global variable: records the length of the longest zigzag pathpublic int longestZigZag(TreeNode root) { res = 0; traverse(root); return res;}void traverse(TreeNode root) { // ... // Directly update the global variable res = Math.max(res, ...);}
Step 3: Write the Recursive Function
Our principle for writing the recursive function is: the function should return as many values as there are subproblems. We decomposed three subproblems in total, and one was extracted as a global variable, so our recursive function needs to return two values.
We can write the basic framework of the binary tree traversal code:
int res; // Global variable: records the length of the longest zigzag pathpublic int longestZigZag(TreeNode root) { res = 0; traverse(root); return res;}// Returns two values// Return value 0: length of the longest left-zig root path// Return value 1: length of the longest right-zig root pathint[] traverse(TreeNode root) { // ...}
How do we write the internals of the recursive function? Simple — just apply the recurrence formulas from earlier.
int res; // Global variable: records the length of the longest zigzag pathpublic int longestZigZag(TreeNode root) { res = 0; traverse(root); return res - 1;}// Returns two values// Return value 0: length of the longest left-zig root path// Return value 1: length of the longest right-zig root pathint[] traverse(TreeNode root) { // Base case: left-zig and right-zig path lengths of an empty subtree are 0 if (root == null) { return new int[]{0, 0}; } // Recursively compute subproblems for left and right subtrees int[] left = traverse(root.left); int[] right = traverse(root.right); // Apply the formulas int leftzz = 1 + left[1]; int rightzz = 1 + right[0]; // Update global variable (primary subproblem) res = Math.max(res, leftzz); res = Math.max(res, rightzz); // Return values (two auxiliary subproblems) return new int[]{leftzz, rightzz};}
Nice! A complex problem solved step by step, just like that.
Maximum Sum BST in Binary Tree
Problem description:
Given a binary tree, find the maximum node sum among all binary search subtrees.
A binary search tree (BST) is defined as:
All values in a node’s left subtree are less than the node’s value;
All values in a node’s right subtree are greater than the node’s value;
Both the left and right subtrees of a node are binary search trees.
Problem example
Seeing the Hard difficulty tag might make you a bit nervous. Don’t worry — let’s continue applying the three-step method to dissect the problem piece by piece!
Step 1: Decompose Subproblems
This problem’s description is a bit convoluted, so let’s first clarify a few concepts:
A BST subtree is a subtree that satisfies the binary search tree property
The node sum of a tree equals the sum of all node values in the tree
What we need to compute is the maximum node sum among all BST subtrees.
Following our established approach, we can decompose the subproblems as:
How do we determine whether the current binary tree is a BST?
This involves two subproblems — the maximum and minimum values of the binary tree. Their recurrence formulas are:
Finally, we also need to compute the node sum. The recurrence formula for the node sum of a binary tree is:
As you can see, this problem involves quite a few subproblems with complex recurrence formulas — worthy of its Hard difficulty rating. However, don’t be intimidated by all these formulas. The purpose of decomposing subproblems is mainly to count exactly how many subproblems there are. And now that we’ve written out all the formulas, writing the code later will be much easier — we can just translate directly from these formulas.
From the decomposition above, this problem involves five subproblems in total:
Maximum BST subtree node sum
Node sum of the binary tree
Whether it is a BST
Minimum value of the binary tree
Maximum value of the binary tree
Step 2: Extract Global Variables
Using the same approach, let’s look at the final result the problem asks for: the maximum node sum among all BST subtrees. Clearly, we can use a global variable to store this value. Each time we find a BST subtree, if its node sum is greater than the global variable, we update it. This way, we can eliminate the first subproblem, “maximum BST subtree node sum.”
Step 3: Write the Recursive Function
After removing one subproblem from five, four remain. So our recursive function needs to return four values.
Here we encounter a new issue: among the four subproblems, “whether it is a BST” returns a bool type, while the others return int types. They can’t conveniently be returned together in a single array. No problem though — in Java, there’s nothing that can’t be solved by writing a class…
class TreeInfo { boolean isBST; // Subproblem: whether it is a BST int min; // Subproblem: minimum value of the binary tree int max; // Subproblem: maximum value of the binary tree int sum; // Subproblem: node sum of the binary tree}
We can have the recursive function return a TreeInfo object to bundle four return values together. Of course, Python users can return four values directly without writing a class.
The final solution code is as follows:
// A class to wrap the four return values of the recursive functionclass TreeInfo { boolean isBST; int min; int max; int sum; TreeInfo(boolean isBST, int min, int max, int sum) { this.isBST = isBST; this.min = min; this.max = max; this.sum = sum; }}int maxSum; // Global variable: records the maximum node sum among BST subtreespublic int maxSumBST(TreeNode root) { maxSum = 0; traverse(root); return maxSum;}TreeInfo traverse(TreeNode root) { // Base case: an empty subtree is a BST, min/max don't exist, sum is 0 if (root == null) { return new TreeInfo(true, Integer.MAX_VALUE, Integer.MIN_VALUE, 0); } // Recursively compute subproblems for left and right subtrees TreeInfo left = traverse(root.left); TreeInfo right = traverse(root.right); // Apply formula: compute node sum int sum = root.val + left.sum + right.sum; // Apply formula: determine whether it is a BST if (left.isBST && right.isBST && left.max < root.val && root.val < right.min) { // Current subtree is a BST maxSum = Math.max(maxSum, sum); // Apply formula: compute min and max of the binary tree int min = Math.min(left.min, root.val); int max = Math.max(right.max, root.val); return new TreeInfo(true, min, max, sum); } else { // Current subtree is not a BST return new TreeInfo(false, Integer.MAX_VALUE, Integer.MIN_VALUE, sum); }}
Summary
Many times, when we encounter a binary tree problem, we can think of some initial ideas, but why do we end up failing to solve it? Because we’re afraid of the complexity, because we get confused by all the conditions and logic.
The point of this article is to help you understand one thing: while some binary tree problems are complex, the approach is systematic. As long as you write out the recurrence relations for all subproblems, extract global variables, and have the function return as many values as there are subproblems, you’ll be able to write correct code. It’s like a math exam — if you’ve mastered all the concepts and it’s just a matter of more computation, would you really be afraid of it?
There are many binary tree problems on LeetCode. If you want to practice systematically and improve, find all problems tagged with “Binary Tree” and try to decompose each one into subproblems and write out the recurrence relations. After solving enough binary tree problems, you’ll realize the patterns are quite limited.
