Post-order Traversal (Iterative using 2 stacks) - Binary Tree

We can do a post-order traversal of a binary tree iteratively using two stacks. Here's a possible implementation:

void postorder(Node *root) {
  if (root == nullptr) return;

  stack<Node *> st, result;
  st.push(root);

  while (!st.empty()) {
    Node *curr = st.top();
    st.pop();
    result.push(curr);
    if (curr->left != nullptr) {
      st.push(curr->left);
    }
    if (curr->right != nullptr) {
      st.push(curr->right);
    }
  }

  while (!result.empty()) {
    cout << result.top()->value << '\n';
    result.pop();
  }
}

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 loops. See the video for more detail.

Space complexity

The space complexity is O(n) (where n is the number of nodes in the tree) because of the space taken by the two stacks. See the video for more detail.

Video with explanation