Binary Tree Postorder Traversal: Explanation and Morris Traversal Implementations in C++, C, and Python

During a recent interview at a well‑known automotive company, a candidate was asked about the postorder traversal of a binary tree and answered "left → right → root"; the interviewer claimed this was incorrect, leading to confusion about the proper definition.

The article revisits the three classic binary‑tree traversals: preorder (root → left → right), inorder (left → root → right), and postorder (left → right → root). All three visit the left subtree before the right subtree, differing only in the position of the root node.

It notes that the candidate's answer is technically correct for postorder, and the interviewer's objection may stem from a misunderstanding or a deliberate trick question, as reflected by various humorous comments from other netizens.

Beyond the basic definitions, the article introduces the Morris traversal technique for postorder, which achieves O(1) extra space by temporarily modifying the tree structure. This method is highlighted as a classic approach covered in the fourth chapter of "Algorithm Secrets".

public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> posList;
        TreeNode *cur = root; // record current node
        while (cur) {
            if (cur->left == nullptr) { // left child absent
                cur = cur->right;
            } else {
                TreeNode *pre = cur->left;
                while (pre->right && pre->right != cur)
                    pre = pre->right;
                if (pre->right == nullptr) { // first visit
                    pre->right = cur;
                    cur = cur->left;
                } else { // second visit
                    pre->right = nullptr;
                    // 1. reverse‑print the left subtree
                    printList(cur->left, posList);
                    cur = cur->right;
                }
            }
        }
        // 2. reverse‑print the rightmost path from root
        printList(root, posList);
        return posList;
    }

    // reverse‑print helper
    void printList(TreeNode *node, vector<int> &posList) {
        int count = 0;
        while (node) {
            ++count;
            posList.emplace_back(node->val);
            node = node->right;
        }
        reverse(posList.end() - count, posList.end());
    }

// reverse‑print helper for C version
void printList(struct TreeNode *node, int *res, int *returnSize) {
    int count = 0;
    while (node) {
        ++count;
        res[(*returnSize)++] = node->val;
        node = node->right;
    }
    // reverse the collected segment
    for (int i = (*returnSize) - count, j = (*returnSize) - 1; i < j; i++, j--) {
        int tmp = res[i];
        res[i] = res[j];
        res[j] = tmp;
    }
}

int *postorderTraversal(struct TreeNode *root, int *returnSize) {
    *returnSize = 0;
    int *res = malloc(sizeof(int) * 201);
    struct TreeNode *cur = root; // record current node
    while (cur) {
        if (cur->left == NULL) { // left child absent
            cur = cur->right;
        } else {
            struct TreeNode *pre = cur->left;
            while (pre->right && pre->right != cur)
                pre = pre->right;
            if (pre->right == NULL) { // first visit
                pre->right = cur;
                cur = cur->left;
            } else { // second visit
                pre->right = NULL;
                // 1. reverse‑print the left subtree
                printList(cur->left, res, returnSize);
                cur = cur->right;
            }
        }
    }
    // 2. reverse‑print the rightmost path from root
    printList(root, res, returnSize);
    return res;
}

def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    posList = []
    cur = root  # record current node
    while cur:
        if not cur.left:  # left child absent
            cur = cur.right
        else:
            pre = cur.left
            while pre.right and pre.right != cur:
                pre = pre.right
            if not pre.right:  # first visit
                pre.right = cur
                cur = cur.left
            else:  # second visit
                pre.right = None
                # 1. reverse‑print the left subtree
                self.printList(cur.left, posList)
                cur = cur.right
    # 2. reverse‑print the rightmost path from root
    self.printList(root, posList)
    return posList

# reverse‑print helper
def printList(self, node, posList):
    count = 0
    while node:
        count += 1
        posList.append(node.val)
        node = node.right
    # reverse the last 'count' elements
    length = len(posList)
    posList[length - count:length] = posList[length - count:length][::-1]

The article concludes that Morris postorder traversal offers an elegant, space‑efficient solution and that understanding the fundamental traversal orders is essential for technical interviews and algorithmic problem solving.