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 postorderTraversal(TreeNode *root) { vector 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 &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.