Binary Tree Postorder Traversal
Easy · Graphs · Explanation and code example
Morris Traversal
How it works
Similar to the iterative approach that reverses a modified preorder, Morris Traversal for postorder works by performing a reverse preorder traversal (current, right, left) without using extra space for a stack. We use temporary thread links from the leftmost node of the right subtree back to the current node. After the traversal, we reverse the result.
Steps
- Initialize the current node to the root.
- While the current node is not
null:- If the current node has no right child, add its value to the result and move to the left child.
- Otherwise, find the leftmost node in the right subtree.
- If the leftmost node's left pointer is
null, add the current value to the result, set the left pointer to the current node (create thread), and move to the right child. - If the left pointer already points to the current node, remove the thread and move to the left child.
- Reverse the result list to get the correct postorder sequence.
- Return the result list.
Complexity
- Time complexity:
O(n) - Space complexity:
O(1)extra space.O(n)space for the output array.
Things to watch for
Adding Node Value Before Recursing on Children
Postorder requires visiting children before the current node. Adding the value before recursive calls produces preorder traversal instead.
Wrong Child Order in Iterative Approach
In the iterative approach using reversal, you must traverse current -> right -> left, then reverse. Traversing current -> left -> right and reversing gives incorrect results.
Python code example
from typing import List, Optional
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
cur = root
while cur:
if not cur.right:
res.append(cur.val)
cur = cur.left
else:
prev = cur.right
while prev.left and prev.left != cur:
prev = prev.left
if not prev.left:
res.append(cur.val)
prev.left = cur
cur = cur.right
else:
prev.left = None
cur = cur.left
res.reverse()
return res
C++ code example
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode* cur = root;
while (cur) {
if (!cur->right) {
res.push_back(cur->val);
cur = cur->left;
} else {
TreeNode* prev = cur->right;
while (prev->left && prev->left != cur) {
prev = prev->left;
}
if (!prev->left) {
res.push_back(cur->val);
prev->left = cur;
cur = cur->right;
} else {
prev->left = nullptr;
cur = cur->left;
}
}
}
reverse(res.begin(), res.end());
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.