Binary Search Tree in Action (Post-order)

This article is the fifth in the series following Mastering Binary Trees (Guideline). It focuses on the clever use of post-order traversal in binary trees. Here is a recap of the previous discussion on post-order traversal:

The code in the pre-order position can only get data passed from the parent node via function parameters, while the code in the post-order position can get both parameter data and data returned from the child subtrees.

In other words, if you notice that a problem is related to subtrees, you most likely need to set a reasonable definition and return value for the function and write the code in the post-order position.

In fact, binary tree problems are not difficult. They mainly revolve around pre-order, in-order, and post-order traversal frameworks. As long as you arrange what needs to be done at each node properly, you can leave the rest to the recursive framework.

However, for some problems, the time complexity varies with different traversal orders. Especially with post-order code, sometimes it can significantly improve algorithm efficiency.

Let's take a look at the post-order traversal code 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
}

Look at this code framework. When do you think you need to write code in the post-order position?

If the task for the current node depends on the results from its left and right subtrees, you need to use post-order traversal.

Next, I'll explain a classic algorithm problem that clearly demonstrates the usefulness of the post-order position. This is LeetCode problem 1373, "Maximum Sum BST in Binary Tree," with the function signature as follows:

int maxSumBST(TreeNode root);

int maxSumBST(TreeNode* root);

def maxSumBST(root: TreeNode)

func maxSumBST(root *TreeNode) int {
}

var maxSumBST = function(root) {

};