Post-order Traversal

Lets look at the 4 options to traverse a binary tree:

• Depth First Search

  • Pre-order
  • In-order
  • Post-order

• Breadth First Search

  • Level-order

In this post, let’s explore Post-order traversal.

Visualise how it traverse

We first visit the Left Subtree, then the Right subtree and lastly, the Root.

               20
             /    \
          /         \
        100         3
      /     \     /   \
    50      15  250   35
  /
222

r = root
lt = left subtree
rt = right subtree

1. (lt)(rt)r
2. ((lt)(rt)r)(rt)20
3. ((lt)(rt)100)(rt)20
4. (((lt)(rt)r)(rt)100)(rt)20
5. (((lt)(rt)50)(rt)100)(rt)20
6. (((222)50)(rt)100)(rt)20
7. (((222)50)(15)100)(rt)20
8. (((222)50)(15)100)((lt)(rt)r)20
9. (((222)50)(15)100)((lt)(rt)3)20
10. (((222)50)(15)100)((250)(35)3)20

Answer: 222, 50, 15, 100, 250, 35, 3, 20

Code Algorithm

Here’s the code example to implmenent a Post-ordertraversal.

type BinaryNode = {
  val: string;
  left?: BinaryNode;
  right?: BinaryNode;
};

function postOrder(root: BinaryNode): void {
  if (!root) throw new Error();

  postOrder(root.left);
  postOrder(root.right);
  console.log(root.val);
}