Post-order Traversal (Iterative using 1 stack) - Binary Tree
We can do a post-order traversal of a binary tree iteratively using only one stack. Here's a possible implementation:
void postorder(Node *root) {
Node *curr = root;
stack<Node *> st;
while (true) {
if (curr != nullptr) {
st.push(curr);
curr = curr->left;
} else {
if (st.empty()) break;
curr = st.top()->right;
if (curr == nullptr) {
Node *last = nullptr;
while (!st.empty() && st.top()->right == last) {
last = st.top();
st.pop();
cout << last->value << '\n';
}
}
}
}
}
Time complexity
The time complexity is O(n) (where n is the number of nodes in the tree) because of the work we do in the while loop. See the video for more detail.
Space complexity
The space complexity is O(h) (where h is the height of the tree) because of the space taken by the stack. See the video for more detail.