Thinking Recursion Algorithms from Binary Tree Perspective

The structure of my historical public account articles is built according to the framework proposed in Framework Thinking for Learning Data Structures and Algorithms. This framework emphasizes the importance of binary tree problems, which is why this article is included in the must-read series of the first chapter.

After solving problems for many years, I condensed the essence of binary tree algorithms into a comprehensive guide here. Although the language might not be very professional and no textbook might include my summarized experiences, currently, no binary tree problem on any problem-solving platform falls outside the framework defined in this article. If you find a problem incompatible with the framework provided here, please leave a comment to let me know.

Let's summarize at the beginning: there are two thinking patterns for solving binary tree problems:

1. Can you get the answer by traversing the binary tree once? If yes, use a traverse function with external variables to achieve this. This is called the "traversal" thinking pattern.

2. Can you define a recursive function that derives the answer to the original problem from the answers to sub-problems (subtrees)? If yes, write out the definition of this recursive function and make full use of its return value. This is called the "decomposition" thinking pattern.

Regardless of which thinking pattern you use, you need to consider:

If you extract a single binary tree node, what does it need to do? When (pre/in/post-order) does it need to do it? You don't have to worry about other nodes; the recursive function will help you perform the same operation on all nodes.

In this article, I will use problems as examples, but they will be the simplest ones, so don't worry about not understanding them. I can help you extract the commonalities of all binary tree problems from the simplest ones and elevate the thinking involved in binary trees. This thinking can be applied to Dynamic Programming, Backtracking Algorithms, Divide and Conquer Algorithms, and Graph Theory Algorithms. This is why I always emphasize framework thinking. I hope that after learning the advanced algorithms mentioned above, you can come back and review this article for a deeper understanding.

First, I must tirelessly emphasize the importance of the binary tree data structure and its related algorithms.

The Importance of Binary Trees

For example, consider two classic sorting algorithms: Quick Sort and Merge Sort. What do you understand about them?

If you tell me that Quick Sort is essentially a pre-order traversal of a binary tree, and Merge Sort is a post-order traversal of a binary tree, then I would know you are an algorithm expert.

Why do Quick Sort and Merge Sort relate to binary trees? Let's briefly analyze their algorithmic concepts and code structures:

The logic of Quick Sort is that to sort nums[lo..hi], we first find a pivot p. By swapping elements, we ensure that nums[lo..p-1] are all less than or equal to nums[p], and nums[p+1..hi] are all greater than nums[p]. Then, we recursively find new pivots in nums[lo..p-1] and nums[p+1..hi]. Eventually, the entire array is sorted.

The code structure for Quick Sort is as follows:

void sort(int[] nums, int lo, int hi) {
    // ****** pre-order traversal position ******
    // construct the partition point p by swapping elements
    int p = partition(nums, lo, hi);
    // ************************

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

void sort(vector<int>& nums, int lo, int hi) {
    // ****** Preorder traversal position ******
    // construct the partition point p by swapping elements
    int p = partition(nums, lo, hi);
    // ************************

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

def sort(nums: list, lo: int, hi: int):
    if lo >= hi:
        return
    # ****** pre-order traversal position ******
    # construct the partition point p by swapping elements
    p = partition(nums, lo, hi)
    # ************************
    
    sort(nums, lo, p - 1)
    sort(nums, p + 1, hi)

func sort(nums []int, lo int, hi int) {
    // ****** Preorder traversal position ******
    // Construct the partition point p by swapping elements
    p := partition(nums, lo, hi)
    // ************************

    sort(nums, lo, p - 1)
    sort(nums, p + 1, hi)
}

var sort = function(nums, lo, hi) {
    // ****** Preorder traversal position ******
    // construct the partition point p by swapping elements
    var p = partition(nums, lo, hi);
    // ************************

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

First, construct the pivot point, then construct pivot points for the left and right subarrays. Doesn't this resemble a preorder traversal of a binary tree?

Now, let's talk about the logic of merge sort. To sort nums[lo..hi], we first sort nums[lo..mid], then sort nums[mid+1..hi], and finally merge these two sorted subarrays. The entire array will then be sorted.

The framework for merge sort is as follows:

// Definition: sort nums[lo..hi]
void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    // sort nums[lo..mid]
    sort(nums, lo, mid);
    // sort nums[mid+1..hi]
    sort(nums, mid + 1, hi);

    // ****** Post-order position ******
    // merge nums[lo..mid] and nums[mid+1..hi]
    merge(nums, lo, mid, hi);
    // *********************
}

// Definition: sort nums[lo..hi]
void sort(vector<int>& nums, int lo, int hi) {
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    // sort nums[lo..mid]
    sort(nums, lo, mid);
    // sort nums[mid+1..hi]
    sort(nums, mid + 1, hi);

    // ****** Post-order position ******
    // merge nums[lo..mid] and nums[mid+1..hi]
    merge(nums, lo, mid, hi);
    // *********************
}

def sort(nums: List[int], lo: int, hi: int) -> None:
    # definition: sort nums[lo..hi]
    mid = (lo + hi) // 2
    # sort nums[lo..mid]
    sort(nums, lo, mid)
    # sort nums[mid+1..hi]
    sort(nums, mid + 1, hi)

    # ****** post-order position ******
    # merge nums[lo..mid] and nums[mid+1..hi]
    merge(nums, lo, mid, hi)
    # *********************

// definition: sort nums[lo..hi]
func sort(nums []int, lo int, hi int) {
    mid := (lo + hi) / 2
    // sort nums[lo..mid]
    sort(nums, lo, mid)
    // sort nums[mid+1..hi]
    sort(nums, mid + 1, hi)

    // ****** post-order position ******
    // merge nums[lo..mid] and nums[mid+1..hi]
    merge(nums, lo, mid, hi)
    // *********************
}

var sort = function(nums, lo, hi) {
    // definition: sort nums[lo..hi]
    var mid = Math.floor((lo + hi) / 2);  
    // sort nums[lo..mid]
    sort(nums, lo, mid);
    // sort nums[mid+1..hi]
    sort(nums, mid + 1, hi);

    // ****** postorder position ******
    // merge nums[lo..mid] and nums[mid+1..hi]
    merge(nums, lo, mid, hi);
    // *********************
}

First, sort the left and right subarrays, then merge them (similar to the logic of merging sorted linked lists). Doesn't this resemble the post-order traversal framework of a binary tree? Moreover, isn't this the famed divide-and-conquer algorithm? It's just that simple.

If you can instantly see through these sorting algorithms, do you still need to memorize these classic algorithms? No. You can effortlessly extend algorithms from the binary tree traversal framework.

All this is to say that the algorithmic concepts of binary trees are widely applicable. In fact, as long as recursion is involved, it can often be abstracted into a binary tree problem.

Next, we'll start with pre-order, in-order, and post-order traversals of binary trees to help you deeply understand the charm of this data structure.

In-Depth Understanding of Pre-order, In-order, and Post-order Traversals

Let me present you with a few questions to ponder for 30 seconds:

1. What is your understanding of pre-order, in-order, and post-order traversals of binary trees? Are they just three different orders of lists?
2. Please analyze, what is special about post-order traversal?
3. Please analyze, why doesn't a multi-way tree have an in-order traversal?

If you can't answer these, it means your understanding of pre-order, in-order, and post-order traversal is limited to textbooks. But don't worry, I'll explain my view of these traversals through analogies.

First, let's review the binary tree recursive traversal framework mentioned in DFS/BFS Traversal of Binary Trees:

void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // pre-order position
    traverse(root.left);
    // in-order position
    traverse(root.right);
    // post-order position
}

void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // pre-order position
    traverse(root->left);
    // in-order position
    traverse(root->right);
    // post-order position
}

def traverse(root):
    if root is None:
        return
    # pre-order position
    traverse(root.left)
    # in-order position
    traverse(root.right)
    # post-order position

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // pre-order position
    traverse(root.Left)
    // in-order position
    traverse(root.Right)
    // post-order position
}

var traverse = function(root) {
    if (root == null) {
        return;
    }
    // pre-order position
    traverse(root.left);
    // in-order position
    traverse(root.right);
    // post-order position
};

Let's put aside the terms like pre-order, in-order, and post-order for now. Just by looking at the traverse function, what do you think it does?

In fact, it is simply a function that traverses all the nodes of a binary tree, not fundamentally different from how you traverse an array or a linked list:

// iterate through the array
void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {

    }
}

// recursively traverse the array
void traverse(int[] arr, int i) {
    if (i == arr.length) {
        return;
    }
    // pre-order position
    traverse(arr, i + 1);
    // post-order position
}

// iterate through the singly linked list
void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {

    }
}

// recursively traverse the singly linked list
void traverse(ListNode head) {
    if (head == null) {
        return;
    }
    // pre-order position
    traverse(head.next);
    // post-order position
}

// iterative traversal of the array
void traverse(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {

    }
}

// recursive traversal of the array
void traverse(vector<int>& arr, int i) {
    if (i == arr.size()) {
        return;
    }
    // pre-order position
    traverse(arr, i + 1);
    // post-order position
}

struct ListNode {
    int val;
    ListNode *next;
};

// iterative traversal of the singly linked list
void traverse(ListNode* head) {
    for (ListNode* p = head; p != nullptr; p = p->next) {

    }
}

// recursive traversal of the singly linked list
void traverse(ListNode* head) {
    if (head == nullptr) {
        return;
    }
    // pre-order position
    traverse(head->next);
    // post-order position
}

# iterate through the array
def traverse(arr: List[int]) -> None:
    for i in range(len(arr)):
        pass

# recursively traverse the array
def traverse_recursive(arr: List[int], i: int) -> None:
    if i == len(arr):
        return
    # pre-order position
    traverse_recursive(arr, i + 1)
    # post-order position


# iterate through the singly linked list
def traverse_linked_list(head: ListNode) -> None:
    p = head
    while p:
        p = p.next

# recursively traverse the singly linked list
def traverse_linked_list_recursive(head: ListNode) -> None:
    if not head:
        return
    # pre-order position
    traverse_linked_list_recursive(head.next)
    # post-order position

// iterate through the array
func traverse(arr []int) {
    for i := 0; i < len(arr); i++ {

    }
}

// recursively traverse the array
func traverse(arr []int, i int) {
    if i == len(arr) {
        return;
    }
    // pre-order position
    traverse(arr, i + 1)
    // post-order position
}


// iterate through the singly linked list
func traverse(head *ListNode) {
    for p := head; p != nil; p = p.Next {

    }
}

// recursively traverse the singly linked list
func traverse(head *ListNode) {
    if head == nil {
        return;
    }
    // pre-order position
    traverse(head.Next)
    // post-order position
}

// iterate through the array
var traverse = function(arr) {
    for (var i = 0; i < arr.length; i++) {

    }
}

// recursively traverse the array
var traverseRecursive = function(arr, i) {
    if (i == arr.length) {
        return;
    }
    // pre-order position
    traverseRecursive(arr, i + 1);
    // post-order position
}


// iterate through the singly linked list
var traverseList = function(head) {
    for (var p = head; p != null; p = p.next) {

    }
}

// recursively traverse the singly linked list
var traverseListRecursive = function(head) {
    if (head == null) {
        return;
    }
    // pre-order position
    traverseListRecursive(head.next);
    // post-order position
}

Traversal of singly linked lists and arrays can be done iteratively or recursively. A binary tree is essentially a binary linked list, and it's not feasible to easily convert it into a for-loop iteration. Therefore, when traversing a binary tree, we typically use recursion.

You may have noticed that any recursive traversal can have a pre-order and a post-order position, occurring before and after the recursion, respectively.

The so-called pre-order position is when you first enter a node (or element), and the post-order position is when you are about to leave a node (or element). Depending on where you place your code, the timing of its execution will differ:

For instance, if you are asked to print all the nodes' values of a singly linked list in reverse order, how would you do it?

There are many ways to implement this, but if you have a deep understanding of recursion, you can use the post-order position to achieve this:

// recursively traverse a singly linked list and print the elements in reverse order
void traverse(ListNode head) {
    if (head == null) {
        return;
    }
    traverse(head.next);
    // post-order position
    print(head.val);
}

// recursively traverse the singly linked list and print elements in reverse order
void traverse(ListNode* head) {
    if (head == nullptr) {
        return;
    }
    traverse(head->next);
    // post-order position
    cout << head->val << endl;
}

# recursively traverse a singly linked list and print the elements in reverse order
def traverse(head):
    if head is None:
        return
    traverse(head.next)
    # post-order position
    print(head.val)

// recursively traverse the singly linked list and print the elements in reverse order
func traverse(head *ListNode) {
    if head == nil {
        return
    }
    traverse(head.Next)
    // post-order position
    fmt.Println(head.Val)
}

// Recursively traverse the singly linked list and print the elements in reverse order
var traverse = function(head) {
    if (head == null) {
        return;
    }
    traverse(head.next);
    // postorder position
    console.log(head.val);
};

Referring to the image above, you should understand why this code can print a singly linked list in reverse order. Essentially, it uses the recursion stack to achieve the effect of reverse traversal.

The same concept applies to binary trees, but with an additional in-order position.

Textbooks typically ask for the results of pre-order, in-order, and post-order traversals. Therefore, someone who has only taken a university data structures course might think that these traversals of a binary tree correspond to three different List<Integer> sequences.

However, I want to emphasize that pre-order, in-order, and post-order represent three specific time points during the traversal of each node in a binary tree, not just three lists in different orders:

• Pre-order code executes as soon as you enter a binary tree node.
• Post-order code executes just before you leave a binary tree node.
• In-order code executes after the left subtree of a binary tree node has been completely traversed and just before starting to traverse the right subtree.

Notice my choice of words; I consistently refer to pre-order, in-order, and post-order "positions" to distinguish them from the commonly mentioned "traversals": you can write code at the pre-order position to add elements to a list, resulting in a pre-order traversal outcome. However, it doesn't mean you can't write more complex code to accomplish more sophisticated tasks.

Illustrated, the pre-order, in-order, and post-order positions on a binary tree look like this:

You can see that each node has a "unique" pre-order, in-order, and post-order position, which is why I say that these traversals are three specific time points for processing each node during a binary tree traversal.

This also explains why multi-branch trees lack an in-order position. In binary trees, each node switches from the left subtree to the right subtree only once, while nodes in multi-branch trees may have many children and switch subtrees multiple times for traversal, resulting in no "unique" in-order position.

All of this foundational information aims to help you build a correct understanding of binary trees. You will realize that:

All binary tree problems are about injecting clever logic at pre-order, in-order, or post-order positions to achieve your goals. You only need to consider what each node should do individually. The rest is handled by the binary tree traversal framework, and the recursion will perform the same operation on all nodes.

You can also observe that Graph Theory Basics extends the binary tree traversal framework to graphs, implementing various classic graph algorithms based on traversal. However, that is a topic for another discussion, which we will not delve into here.

Two Approaches to Problem Solving

In the previous article My Learnings on Algorithms, it was mentioned:

Recursive solutions for binary tree problems can be classified into two approaches. The first approach is to traverse the binary tree to get the answer, and the second is to solve the problem by breaking it down into subproblems. These two approaches correspond to the Core Framework of Backtracking and the Core Framework of Dynamic Programming respectively.

At that time, I used the problem of finding the maximum depth of a binary tree as an example. The focus was on comparing these two approaches with dynamic programming and backtracking algorithms. In this article, the focus is on analyzing how these two approaches solve binary tree problems.

LeetCode Problem 104, "Maximum Depth of Binary Tree," is about finding the maximum depth, which is the number of nodes along the longest path from the root node to the "farthest" leaf node. For example, given this binary tree, the algorithm should return 3:

What is your approach to solving this problem? Clearly, by traversing the binary tree and using an external variable to record the depth of each node, you can get the maximum depth by taking the maximum value. This is the approach of traversing the binary tree to calculate the answer.

The solution code is as follows:

class Solution {
    // record the maximum depth
    int res = 0;

    // record the depth of the traversed node
    int depth = 0;

    public int maxDepth(TreeNode root) {
        traverse(root);
        return res;
    }

    // binary tree traversal framework
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // pre-order position
        depth++;
        if (root.left == null && root.right == null) {
            // reached a leaf node, update the maximum depth
            res = Math.max(res, depth);
        }
        traverse(root.left);
        traverse(root.right);
        // post-order position
        depth--;
    }
}

class Solution {
public:
    // record the maximum depth
    int res = 0;
    // record the depth of the current node
    int depth = 0;

    // main function
    int maxDepth(TreeNode* root) {
        traverse(root);
        return res;
    }

    // binary tree traversal framework
    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        // pre-order position
        depth++;
        if (root->left == nullptr && root->right == nullptr) {
            // reached a leaf node, update the maximum depth
            res = std::max(res, depth);
        }
        traverse(root->left);
        traverse(root->right);
        // post-order position
        depth--;
    }
};

class Solution:
    def __init__(self):
        # record the maximum depth
        self.res = 0
        # record the depth of the traversed node
        self.depth = 0

    def maxDepth(self, root: TreeNode) -> int:
        self.traverse(root)
        return self.res

    # binary tree traversal framework
    def traverse(self, root: TreeNode) -> None:
        if root is None:
            return
        # pre-order position
        self.depth += 1
        if root.left is None and root.right is None:
            # reached a leaf node, update the maximum depth
            self.res = max(self.res, self.depth)
        self.traverse(root.left)
        self.traverse(root.right)
        # post-order position
        self.depth -= 1

// main function
func maxDepth(root *TreeNode) int {
    // record the maximum depth
    var res int = 0

    // record the depth of the traversed node
    var depth int = 0;

    // binary tree traversal framework
    var traverse func(root *TreeNode)
    traverse = func(root *TreeNode) {
        if (root == nil) {
            return
        }
        // pre-order position
        depth++
        if (root.Left == nil && root.Right == nil) {
            // reached leaf node, update maximum depth
            res = max(res, depth)
        }
        traverse(root.Left)
        traverse(root.Right)
        // post-order position
        depth--
    }

    traverse(root)
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// main function
var maxDepth = function(root) {

    // record the maximum depth
    var res = 0;
    // record the depth of the current node
    var depth = 0;

    // binary tree traversal framework
    var traverse = function(root) {
        if (root == null) {
            return;
        }
        // pre-order position
        depth++;
        if (root.left == null && root.right == null) {
            // reached a leaf node, update the maximum depth
            res = Math.max(res, depth);
        }
        traverse(root.left);
        traverse(root.right);
        // post-order position
        depth--;
    };


    traverse(root);
    return res;
};

This solution should be easy to understand, but why do we need to increase depth at the pre-order position and decrease depth at the post-order position?

As mentioned earlier, the pre-order position is when entering a node, and the post-order position is when leaving a node. The depth records the current depth of the recursive node. You can think of traverse as a pointer moving through the binary tree, so it naturally needs to be maintained this way.

As for updating res, you can place it in the pre-order, in-order, or post-order position, as long as it happens after entering the node and before leaving the node (i.e., after incrementing depth and before decrementing it).

Of course, it's also easy to see that the maximum depth of a binary tree can be derived from the maximum depth of its subtrees. This is the idea of decomposing the problem to calculate the answer.

The solution code is as follows:

class Solution {
    // Definition: Given the root node, return the maximum depth of the binary tree
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // Use the definition to calculate the maximum depth of the left and right subtrees
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        // The maximum depth of the entire tree is
        // the maximum of the left and right subtree
        // plus one for the root node itself
        int res = Math.max(leftMax, rightMax) + 1;

        return res;
    }
}

class Solution {
public:
    // Definition: input the root node and return the maximum depth of this binary tree
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        // Using the definition, calculate the maximum depth of the left and right subtrees
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        // The maximum depth of the entire tree is equal
        // to the maximum depth of the left and right
        // and then add the root node itself
        int res = std::max(leftMax, rightMax) + 1;

        return res;
    }
};

class Solution:
    # Definition: Given the root node, return the maximum depth of this binary tree
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        # Using the definition, calculate the maximum depth of the left and right subtrees
        leftMax = self.maxDepth(root.left)
        rightMax = self.maxDepth(root.right)
        # The maximum depth of the entire tree is
        # the maximum depth of the left and right
        # plus the root node itself
        res = max(leftMax, rightMax) + 1

        return res

// Definition: input the root node, return the maximum depth of this binary tree
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	// Using the definition, calculate the maximum depth of the left and right subtrees
	leftMax := maxDepth(root.Left)
	rightMax := maxDepth(root.Right)
	// The maximum depth of the entire tree is equal to
// the maximum depth of the left and right subtrees,
    // then add the root node itself
	res := max(leftMax, rightMax) + 1

	return res
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

// definition: input the root node, return the maximum depth of this binary tree
var maxDepth = function(root) {
	if (root === null) {
		return 0;
	}
	// use the definition to calculate the maximum depth of the left and right subtrees
	var leftMax = maxDepth(root.left);
	var rightMax = maxDepth(root.right);
	// the maximum depth of the entire tree is equal to
// the maximum depth of the left and right subtrees,
    // then add the root node itself
	var res = Math.max(leftMax, rightMax) + 1;

	return res;
};

As long as you understand the definition of the recursive function, this solution is not difficult to grasp. But why is the main code logic concentrated in the post-order position?

The core of this correct thought process is that you can indeed deduce the depth of the original tree from the maximum depth of the subtrees. Therefore, you should first use the recursive function definition to calculate the maximum depth of the left and right subtrees, and then deduce the maximum depth of the original tree. Naturally, the main logic is placed in the post-order position.

If you understand the two approaches to the maximum depth problem, then let's revisit the basic pre-order, in-order, and post-order traversal of binary trees. For example, in LeetCode problem 144 "Binary Tree Preorder Traversal," you are asked to calculate the pre-order traversal result.

The familiar solution is to use the "traversal" approach, which should be straightforward:

class Solution {
    // store the result of the preorder traversal
    List<Integer> res = new LinkedList<>();

    // return the preorder traversal result
    public List<Integer> preorderTraversal(TreeNode root) {
        traverse(root);
        return res;
    }

    // binary tree traversal function
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // preorder position
        res.add(root.val);
        traverse(root.left);
        traverse(root.right);
    }
}

class Solution {
public:
    // store the result of the preorder traversal
    vector<int> res;

    // return the preorder traversal result
    vector<int> preorderTraversal(TreeNode* root) {
        traverse(root);
        return res;
    }

    // binary tree traversal function
    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        // preorder position
        res.push_back(root->val);
        traverse(root->left);
        traverse(root->right);
    }
};

class Solution:
    def __init__(self):
        self.res = []
    
    # return the result of preorder traversal
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        self.traverse(root)
        return self.res

    # binary tree traversal function
    def traverse(self, root: TreeNode):
        if root is None:
            return
        # preorder position
        self.res.append(root.val)
        self.traverse(root.left)
        self.traverse(root.right)

// preorderTraverse returns the preorder traversal result
func preorderTraversal(root *TreeNode) []int {

    // store the result of the preorder traversal
    var res []int

    // binary tree traversal function
    var traverse func(root *TreeNode)
    traverse = func(root *TreeNode) {
        if root == nil {
            return
        }
        // preorder position
        res = append(res, root.Val)
        traverse(root.Left)
        traverse(root.Right)
    }

    traverse(root)
    return res
}

// return the preorder traversal result
var preorderTraversal = function(root) {
    // store the result of the preorder traversal
    var res = [];

    // binary tree traversal function
    var traverse = function(root) {
        if (root == null) {
            return;
        }
        // preorder position
        res.push(root.val);
        traverse(root.left);
        traverse(root.right);
    };

    traverse(root);
    return res;
}

But can you calculate the result of a preorder traversal using the "problem decomposition" approach?

In other words, without using auxiliary functions like traverse or any external variables, can you solve it recursively using only the provided preorderTraverse function?

We know that the characteristic of preorder traversal is that the root node's value comes first, followed by the preorder traversal of the left subtree, and finally the preorder traversal of the right subtree:

This allows us to decompose the problem: The preorder traversal result of a binary tree = Root node + Preorder traversal of the left subtree + Preorder traversal of the right subtree.

Therefore, you can implement the preorder traversal algorithm like this:

class Solution {
    // Definition: Given the root node of a binary
    // tree, return the preorder traversal result of
    List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        // The result of preorder traversal, root.val is first
        res.add(root.val);
        // Using the function definition, followed by
        // the preorder traversal result of the left
        res.addAll(preorderTraversal(root.left));
        // Using the function definition, finally followed
        // by the preorder traversal result of the right
        res.addAll(preorderTraversal(root.right));

        return res;
    }
}

class Solution {
public:
    // Definition: Given the root node of a binary
    // tree, return the preorder traversal result of
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        // The result of preorder traversal, root->val is the first element
        res.push_back(root->val);
        // Using the function definition, followed by
        // the preorder traversal result of the left
        vector<int> left = preorderTraversal(root->left);
        res.insert(res.end(), left.begin(), left.end());
        // Using the function definition, followed by
        // the preorder traversal result of the right
        vector<int> right = preorderTraversal(root->right);
        res.insert(res.end(), right.begin(), right.end());

        return res;
    }
};

class Solution:
    # Definition: Given the root of a binary tree, return the preorder traversal of this tree
    def preorderTraversal(self, root):
        res = []
        if root == None:
            return res
        # In the preorder traversal result, root.val is the first
        res.append(root.val)
        # Use the function definition to append
        # the preorder traversal result of the left
        res.extend(self.preorderTraversal(root.left))
        # Use the function definition to append
        # the preorder traversal result of the
        res.extend(self.preorderTraversal(root.right)) 

        return res

// Definition: Given the root of a binary tree,
// return the preorder traversal result of this
func preorderTraversal(root *TreeNode) []int {
	var res []int
	if root == nil {
		return res
	}
	// In preorder traversal, root.Val is the first element.
	res = append(res, root.Val)
	// According to the function definition, append the
// preorder traversal result of the left subtree.
	res = append(res, preorderTraversal(root.Left)...)
	// According to the function definition, append the
// preorder traversal result of the right subtree.
	res = append(res, preorderTraversal(root.Right)...)

	return res
}

// Definition: Given the root node of a binary tree,
// return the preorder traversal result of this tree
var preorderTraversal = function(root) {
    var res = [];
    if (root == null) {
        return res;
    }
    // The result of preorder traversal, root.val is the first
    res.push(root.val);
    // Using function definition, followed by the preorder traversal result of the left subtree
    res = res.concat(preorderTraversal(root.left));
    // Using function definition, finally followed by
    // the preorder traversal result of the right
    res = res.concat(preorderTraversal(root.right));

    return res;
}

In-order and post-order traversals are similar; you just need to place add(root.val) in the corresponding position for in-order and post-order.

This method is concise and effective, but why is it not commonly used?

One reason is that the complexity of this algorithm is hard to control and it heavily depends on language features.

In Java, whether you use ArrayList or LinkedList, the complexity of the addAll method is O(N), so the overall worst-case time complexity can reach O(N^2). Unless you implement an addAll method with a complexity of O(1) yourself, which is achievable with linked lists since multiple linked lists can be connected with simple pointer operations.

Of course, the main reason is that this method is never taught in textbooks...

The above mentioned two simple examples, but there are many binary tree problems that can be solved using both approaches. This requires you to practice and think more, rather than just being satisfied with one familiar solution approach.

To sum up, the general thought process when encountering a binary tree problem is:

1. Can the answer be obtained by traversing the binary tree once? If so, use a traverse function combined with external variables.

2. Can you define a recursive function that derives the solution to the original problem from the solutions to subproblems (subtrees)? If so, write the definition of this recursive function and make full use of its return value.

3. Regardless of which mindset you use, you need to understand what each node of the binary tree needs to do and when (pre-order, in-order, post-order) it needs to do it.

Our site lists over 100 binary tree problems in the Binary Tree Recursion Practice, using the above two mindsets to guide you step-by-step, helping you fully grasp recursive thinking and understand advanced algorithms more easily.

The Special Nature of Postorder Position

Before discussing postorder, let's briefly touch on preorder and inorder.

Preorder itself doesn't have any special properties. The reason why many problems seem to be solved at the preorder position is that we habitually write code that is insensitive to the preorder, inorder, and postorder positions in the preorder position.

Inorder is mainly used in BST scenarios. You can entirely think of the inorder traversal of a BST as traversing a sorted array.

Let's look at some specific examples to feel the difference in their capabilities. Given a binary tree, here are two simple questions:

1. If the root node is considered level 1, how do you print the level number of each node?
2. How do you print the number of nodes in the left and right subtrees of each node?

The code for the first question can be written like this:

// Binary tree traversal function
void traverse(TreeNode root, int level) {
    if (root == null) {
        return;
    }
    // Pre-order position
    printf("Node %s at level %d", root.val, level);
    traverse(root.left, level + 1);
    traverse(root.right, level + 1);
}

// Call it like this
traverse(root, 1);

// Binary tree traversal function
void traverse(TreeNode* root, int level) {
    if (root == nullptr) {
        return;
    }
    // Pre-order position
    printf("Node %d at level %d", root->val, level);
    traverse(root->left, level + 1);
    traverse(root->right, level + 1);
}

// Call it like this
traverse(root, 1);

# binary tree traversal function
def traverse(root, level):
    if root is None:
        return
    # pre-order position
    print(f"Node {root.val} at level {level}")
    traverse(root.left, level + 1)
    traverse(root.right, level + 1)

# call it like this
traverse(root, 1)

// binary tree traversal function
func traverse(root *TreeNode, level int) {
    if root == nil {
        return
    }
    // pre-order position
    fmt.Printf("Node %v at level %v\n", root.Val, level)
    traverse(root.Left, level + 1)
    traverse(root.Right, level + 1)
}

// call it like this
traverse(root, 1)

// binary tree traversal function
var traverse = function(root, level) {
    if (root == null) {
        return;
    }
    // pre-order position
    console.log("Node " + root.val + " at level " + level);
    traverse(root.left, level + 1);
    traverse(root.right, level + 1);
}

// call it like this
traverse(root, 1);

The second problem can be coded like this:

// Definition: Given a binary tree, return the total number of nodes in the tree
int count(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftCount = count(root.left);
    int rightCount = count(root.right);
    // Post-order position
    printf("节点 %s 的左子树有 %d 个节点，右子树有 %d 个节点",
            root, leftCount, rightCount);

    return leftCount + rightCount + 1;
}

// Definition: Given a binary tree, return the total number of nodes in the tree
int count(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftCount = count(root->left);
    int rightCount = count(root->right);
    // Post-order position
    printf("节点 %p 的左子树有 %d 个节点，右子树有 %d 个节点",
            root, leftCount, rightCount);

    return leftCount + rightCount + 1;
}

# Definition: Given a binary tree, return the total number of nodes in this binary tree
def count(root):
    if root is None:
        return 0
    leftCount = count(root.left)
    rightCount = count(root.right)
    # postorder position
    print(f"节点 {root} 的左子树有 {leftCount} 个节点，右子树有 {rightCount} 个节点")
    
    return leftCount + rightCount + 1

// Definition: Given a binary tree, return the total number of nodes in the tree
func count(root *TreeNode) int {
    if root == nil {
        return 0
    }

    leftCount := count(root.Left)
    rightCount := count(root.Right)

    // post-order position
    fmt.Printf("节点 %v 的左子树有 %d 个节点，右子树有 %d 个节点\n",
            root, leftCount, rightCount)

    return leftCount + rightCount + 1
}

// Definition: given a binary tree, return the total number of nodes in this binary tree
var count = function(root) {
    if (root == null) {
        return 0;
    }
    var leftCount = count(root.left);
    var rightCount = count(root.right);
    // post-order position
    console.log(`节点 ${root} 的左子树有 ${leftCount} 个节点，右子树有 ${rightCount} 个节点`);

    return leftCount + rightCount + 1;
};

Next, let's see how the postorder position plays a role in actual problems by briefly discussing LeetCode problem 543, "Diameter of Binary Tree," which requires you to calculate the longest diameter of a binary tree.

The "diameter" of a binary tree is the length of the path between any two nodes. The longest "diameter" does not necessarily pass through the root node. For example, in the binary tree below:

Its longest diameter is 3, which can be the length of paths like [4,2,1,3], [4,2,1,9], or [5,2,1,3].

The key to solving this problem is that the "diameter" length of each binary tree is the sum of the maximum depths of the left and right subtrees of a node.

To find the longest "diameter" in the entire tree, a straightforward approach is to traverse every node in the tree, calculate the "diameter" at each node by summing the maximum depths of its left and right subtrees, and finally determine the maximum "diameter" among them.

We have previously implemented the maximum depth algorithm, and based on this idea, we can write the following code:

class Solution {
    // record the length of the maximum diameter
    int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        // calculate the diameter for each node and find the maximum diameter
        traverse(root);
        return maxDiameter;
    }

    // traverse the binary tree
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // calculate the diameter for each node
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        int myDiameter = leftMax + rightMax;
        // update the global maximum diameter
        maxDiameter = Math.max(maxDiameter, myDiameter);
        
        traverse(root.left);
        traverse(root.right);
    }

    // calculate the maximum depth of the binary tree
    int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        return 1 + Math.max(leftMax, rightMax);
    }
}

class Solution {
public:
    // record the length of the maximum diameter
    int maxDiameter = 0;

    int diameterOfBinaryTree(TreeNode* root) {
        // calculate the diameter for each node and find the maximum diameter
        traverse(root);
        return maxDiameter;
    }

private:
    // traverse the binary tree
    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        // calculate the diameter for each node
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        int myDiameter = leftMax + rightMax;
        // update the global maximum diameter
        maxDiameter = max(maxDiameter, myDiameter);

        traverse(root->left);
        traverse(root->right);
    }

    // calculate the maximum depth of the binary tree
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        return 1 + max(leftMax, rightMax);
    }
};

class Solution:

    def __init__(self):
        # record the length of the maximum diameter
        self.maxDiameter = 0

    def diameterOfBinaryTree(self, root):
        # calculate the diameter for each node, find the maximum diameter
        self.traverse(root)
        return self.maxDiameter

    # traverse the binary tree
    def traverse(self, root):
        if root is None:
            return
        # calculate the diameter for each node
        leftMax = self.maxDepth(root.left)
        rightMax = self.maxDepth(root.right)
        myDiameter = leftMax + rightMax
        # update the global maximum diameter
        self.maxDiameter = max(self.maxDiameter, myDiameter)
        
        self.traverse(root.left)
        self.traverse(root.right)

    # calculate the maximum depth of the binary tree
    def maxDepth(self, root):
        if root is None:
            return 0
        leftMax = self.maxDepth(root.left)
        rightMax = self.maxDepth(root.right)
        return 1 + max(leftMax, rightMax)

// record the length of the maximum diameter
func diameterOfBinaryTree(root *TreeNode) int {
    maxDiameter := 0

    // traverse the binary tree
    var traverse func(root *TreeNode)
    traverse = func(root *TreeNode) {
        if root == nil {
            return
        }
        // calculate the diameter for each node
        leftMax := maxDepth(root.Left)
        rightMax := maxDepth(root.Right)
        myDiameter := leftMax + rightMax
        // update the global maximum diameter
        maxDiameter = max(maxDiameter, myDiameter)
        
        traverse(root.Left)
        traverse(root.Right)
    }
    traverse(root)
    return maxDiameter
}

// calculate the maximum depth of the binary tree
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftMax := maxDepth(root.Left)
    rightMax := maxDepth(root.Right)
    return 1 + max(leftMax, rightMax)
}

// helper function to find the maximum of two numbers
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

var diameterOfBinaryTree = function(root) {
    // record the length of the maximum diameter
    let maxDiameter = 0;

    // calculate the maximum depth of the binary tree
    const maxDepth = function(root) {
        if (root === null) {
            return 0;
        }
        let leftMax = maxDepth(root.left);
        let rightMax = maxDepth(root.right);
        return 1 + Math.max(leftMax, rightMax);
    };

    // traverse the binary tree
    const traverse = function(root) {
        if (root === null) {
            return;
        }
        // calculate the diameter for each node
        let leftMax = maxDepth(root.left);
        let rightMax = maxDepth(root.right);
        let myDiameter = leftMax + rightMax;
        // update the global maximum diameter
        maxDiameter = Math.max(maxDiameter, myDiameter);
        
        traverse(root.left);
        traverse(root.right);
    };

    traverse(root);

    return maxDiameter;
};

This solution is correct, but it takes a long time to run. The reason is obvious: the traverse function calls the recursive function maxDepth for each node, and maxDepth needs to traverse all nodes of the subtree. Therefore, the worst-case time complexity is O(N^2).

This situation is what we discussed earlier: the pre-order position cannot obtain subtree information, so each node has to call the maxDepth function to calculate the depth of the subtree.

So how can we optimize it? We should put the logic for calculating the "diameter" in the post-order position. Specifically, it should be placed in the post-order position of maxDepth, because the post-order position of maxDepth knows the maximum depth of the left and right subtrees.

Therefore, by slightly modifying the code logic, we can get a better solution:

class Solution {
    // record the length of the maximum diameter
    int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return maxDiameter;
    }

    int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        // post-order position, calculate the maximum diameter by the way
        int myDiameter = leftMax + rightMax;
        maxDiameter = Math.max(maxDiameter, myDiameter);

        return 1 + Math.max(leftMax, rightMax);
    }
}

class Solution {
    // record the length of the maximum diameter
    int maxDiameter = 0;

public:
    int diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root);
        return maxDiameter;
    }

    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        // post-order position, calculate the maximum diameter along the way
        int myDiameter = leftMax + rightMax;
        maxDiameter = max(maxDiameter, myDiameter);

        return 1 + max(leftMax, rightMax);
    }
};

class Solution:
    def __init__(self):
        # record the length of the maximum diameter
        self.maxDiameter = 0

    def diameterOfBinaryTree(self, root):
        self.maxDepth(root)
        return self.maxDiameter

    def maxDepth(self, root):
        if root is None:
            return 0
        leftMax = self.maxDepth(root.left)
        rightMax = self.maxDepth(root.right)
        # post-order position, by the way, calculate the maximum diameter
        myDiameter = leftMax + rightMax
        self.maxDiameter = max(self.maxDiameter, myDiameter)

        return 1 + max(leftMax, rightMax)

func diameterOfBinaryTree(root *TreeNode) int {
    // record the length of the maximum diameter
    maxDiameter := 0

    var maxDepth func(root *TreeNode) int
    maxDepth = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        leftMax := maxDepth(root.Left)
        rightMax := maxDepth(root.Right)
        // in post-order position, calculate the maximum diameter
        myDiameter := leftMax + rightMax
        maxDiameter = max(maxDiameter, myDiameter)
        return 1 + max(leftMax, rightMax)
    }

    maxDepth(root)

    return maxDiameter
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

var diameterOfBinaryTree = function(root) {
    let maxDiameter = 0;

    const maxDepth = function(root) {
        if (root === null) {
            return 0;
        }
        let leftMax = maxDepth(root.left);
        let rightMax = maxDepth(root.right);
        // in post-order position, calculate the maximum diameter
        let myDiameter = leftMax + rightMax;
        maxDiameter = Math.max(maxDiameter, myDiameter);

        return 1 + Math.max(leftMax, rightMax);
    }

    maxDepth(root);
    return maxDiameter;
};

Now, the time complexity is only O(N) for the maxDepth function.

As mentioned earlier, when dealing with subtree problems, the first thing to think about is setting a return value for the function and then working on it in the post-order position.

Conversely, if you find yourself writing a recursive-in-recursive solution like the one at the beginning, it's likely worth reconsidering if post-order traversal can optimize it.

For more exercises that use the post-order position, refer to Hand-holding Guide to Binary Trees (Post-order Section), Hand-holding Guide to Binary Search Trees (Post-order Section), and Intensive Practice: Solving Problems Using Post-order Position.

Understanding the Differences and Connections between Dynamic Programming, Backtracking, and DFS from a Tree's Perspective

Previously, I mentioned that dynamic programming and backtracking are two different approaches to binary tree algorithms. I believe readers who have reached this point agree with me. However, some attentive readers often ask: Your way of thinking is enlightening, but haven't you talked about the DFS algorithm?

Actually, in the article Mastering All Island Problems in One Go, I used the DFS algorithm, but I haven't dedicated an article solely to DFS. This is because DFS and backtracking algorithms are very similar, differing only in details.

What is this detailed difference? It boils down to whether the "make a choice" and "undo a choice" actions are inside or outside the for-loop. In DFS, they are outside, while in backtracking, they are inside.

Why this difference? It still needs to be understood in the context of binary trees. In this section, I'll explain the three classic algorithmic ideas of backtracking, DFS, and dynamic programming, as well as their connections and differences with binary tree algorithms, in one sentence:

How to understand this? I'll explain each with three examples.

Example One: The Thought Process of Problem Decomposition

First example, given a binary tree, write a count function using problem decomposition to calculate the total number of nodes in this binary tree. The code is straightforward, as mentioned earlier:

// Definition: input a binary tree, return the total number of nodes in this binary tree
int count(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // The current node cares about the total number of nodes in each of its subtrees
    // Because the result of the subproblems can be
    // used to derive the result of the original
    int leftCount = count(root.left);
    int rightCount = count(root.right);
    // In the postorder position, the total number of nodes in the left and right
    // subtrees plus the current node itself is the total number of nodes in the entire
    return leftCount + rightCount + 1;
}

// Definition: Given a binary tree, return the total number of nodes in this binary tree
int count(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    // The current node cares about the total number of nodes in the two subtrees
    // Because the result of the subproblems can derive the result of the original problem
    int leftCount = count(root->left);
    int rightCount = count(root->right);
    // In the post-order position, the number of nodes in the left and
    // right subtrees plus itself is the total number of nodes in the entire
    return leftCount + rightCount + 1;
}

# Definition: Given a binary tree, return the total number of nodes in the tree
def count(root):
    if root is None:
        return 0
    # The current node is concerned with the total number of nodes in its two subtrees
    # Because the result of the subproblems can be
    # used to derive the result of the original
    leftCount = count(root.left)
    rightCount = count(root.right)
    # In the post-order position, the total number of nodes in the left and
    # right subtrees plus the current node equals the total number of nodes in
    return leftCount + rightCount + 1

// Definition: Given a binary tree, return the total number of nodes in the tree
func count(root *TreeNode) int {
    if root == nil {
       return 0
    }
    // The current node cares about the total number of nodes in its left and right subtrees
    // Because the result of the sub-problems can be
    // used to derive the result of the original
    leftCount := count(root.Left)
    rightCount := count(root.Right)
    // In post-order position, the number of nodes in the left and right
    // subtrees plus the current node is the total number of nodes in the
    return leftCount + rightCount + 1
}

// Definition: Given a binary tree, return the total number of nodes in this binary tree
var count = function(root) {
    if (root == null) {
        return 0;
    }
    // The current node cares about the total number of nodes in its two subtrees
    // Because the result of the subproblems can be
    // used to derive the result of the original
    var leftCount = count(root.left);
    var rightCount = count(root.right);
    // In the post-order position, the number of nodes in the left and
    // right subtrees plus itself is the total number of nodes in the entire
    return leftCount + rightCount + 1;
}

You see, this is the idea behind breaking down problems using dynamic programming. It always focuses on subproblems with the same structure, which can be likened to "subtrees" in a binary tree.

Let's look at a specific dynamic programming problem. For example, in the Detailed Explanation of Dynamic Programming Framework, we use the Fibonacci sequence as an example. Our focus is on the return values of each subtree:

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

def fib(N: int) -> int:
    if N == 1 or N == 2: 
        return 1
    return fib(N - 1) + fib(N - 2)

func fib(N int) int {
    if N == 1 || N == 2 {
        return 1
    }
    return fib(N - 1) + fib(N - 2)
}

var fib = function(N) {
    if (N == 1 || N == 2) {
        return 1;
    }
    return fib(N - 1) + fib(N - 2);
}

Example 2: Demonstrating the Concept of Backtracking Algorithm

Second Example, given a binary tree, write a traverse function using traversal logic that prints the process of traversing this binary tree. Take a look at the code:

void traverse(TreeNode root) {
    if (root == null) return;
    printf("从节点 %s 进入节点 %s", root, root.left);
    traverse(root.left);
    printf("从节点 %s 回到节点 %s", root.left, root);

    printf("从节点 %s 进入节点 %s", root, root.right);
    traverse(root.right);
    printf("从节点 %s 回到节点 %s", root.right, root);
}

void traverse(TreeNode* root) {
    // If the node is null (indicating it has passed the leaf node), return
    if (root == nullptr) return;
    // Start from node root and move along the left side
    printf("从节点 %s 进入节点 %s", root, root->left);
    traverse(root->left);
    // Return from the left side of node root
    printf("从节点 %s 回到节点 %s", root->left, root);

    // Start from node root and move along the right side
    printf("从节点 %s 进入节点 %s", root, root->right);
    traverse(root->right);
    // Return from the right side of node root
    printf("从节点 %s 回到节点 %s", root->right, root);
}