Binary Search Tree in Action (Post-order)

This article is the fifth part following Binary Tree Key Points (Summary). It mainly talks about the power of post-order in binary trees. Here is a summary about post-order traversal from the previous article:

In pre-order, the code can only get data passed from the parent node through function parameters. In post-order, the code can not only get parameter data, but also the results returned by the left and right subtrees.

In other words, if the problem is related to subtrees, you should define your function carefully and write code in the post-order position.

Actually, binary tree problems are not hard. They are just about using pre-order, in-order, and post-order frameworks. As long as you arrange what each node should do, you can leave the rest to recursion.

But for some problems, different traversal orders have different time complexity. Especially code written in post-order can sometimes make your algorithm much faster.

Let's look again at the post-order traversal framework:

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
    // the position of the post-order code
    // process the current node here
}

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    
    traverse(root->left);
    traverse(root->right);
    
    // the position of post-order code
    // process the current node here
}

def traverse(root):
    if not root:
        return
    traverse(root.left)
    traverse(root.right)
    # position of post-order code
    # process the current node here

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    traverse(root.Right)
    // the position of the post-order code
    // process the current node here
}

var traverse = function(root) {
    if (root === null) return;
    traverse(root.left);
    traverse(root.right);
    // the position of the post-order code
    // process the current node here
}

Based on this framework, when should you write code in the post-order position?

If what the current node needs to do depends on the results of its left and right subtrees, you should use post-order traversal.

Next, let's look at a classic algorithm problem to see the power of post-order. This is LeetCode 1373: Maximum Sum BST in Binary Tree. The function signature is:

int maxSumBST(TreeNode root);

int maxSumBST(TreeNode* root);

def maxSumBST(root: TreeNode)

func maxSumBST(root *TreeNode) int {
}

var maxSumBST = function(root) {

};

Problem Analysis

Approach

Optimizing the Solution

Summary