SimuVedaAlgorithms Lab Open in the lab

Trees / Beginner

Postorder Traversal Visualizer

Both subtrees first, the node last.

Start the Postorder Traversal simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(h)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Postorder traversal: left subtree, right subtree and the node itself, in the order shown in the code.
  2. At node 50.
  3. Go left from 50.
  4. At node 30.
  5. Go left from 30.
  6. At node 20.
  7. Visit 20.
  8. Back at 30.
  9. Go right from 30.
  10. At node 40.
  11. Go left from 40.
  12. At node 35.
  13. Visit 35.
  14. Back at 40.
  15. Visit 40.
  16. Back at 30.
  17. Visit 30.
  18. Back at 50.
  19. Go right from 50.
  20. At node 70.
  21. … 12 more steps …
  22. Visit 70.
  23. Back at 50.
  24. Visit 50.
  25. Done. Visit order: 20, 35, 40, 30, 65, 60, 80, 70, 50.

Try it with your own input →

Postorder traversal in Java, Python, C++, C and JavaScript

void postorder(Node n) {
  if (n == null) return;
  postorder(n.left);
  postorder(n.right);
  visit(n);
}
def postorder(n):
    if n is None:
        return
    postorder(n.left)
    postorder(n.right)
    visit(n)
void postorder(Node* n) {
  if (!n) return;
  postorder(n->left);
  postorder(n->right);
  visit(n);
}
void postorder(struct Node* n) {
  if (n == NULL) return;
  postorder(n->left);
  postorder(n->right);
  visit(n);
}
function postorder(n) {
  if (n === null) return;
  postorder(n.left);
  postorder(n.right);
  visit(n);
}

In an interview

Use postorder when a parent needs answers from its children: tree height, diameter, deleting a tree.

More trees