Postorder Traversal


Can you explain how to perform post order traversal on a binary tree and provide a code implementation?

Background: Post-order traversal is a way of traversing a binary tree where the algorithm traverses the left subtree first, followed by the right subtree, and then visits the root node. This algorithm is often used to delete a tree. It is important to have a good understanding of building a binary tree to implement this algorithm.

Sample Input/Output:

   /  \
  25  125
 / \   / \
20 30 60  70
    /    /  \
   33   40  90

20 30 25 33 40 30 60 90 70 125 50


To implement post-order traversal on a binary tree, we first need to create a node class and a binary tree class. We then need to create a post-order traversal method within the binary tree class. Here is an implementation in JavaScript:

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;

class BinaryTree {
  constructor() {
    this.root = null;

  insert(data) {
    const newNode = new Node(data);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);

  insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);

  postOrder(node) {
    if (node === null) {
class defines a node in the binary tree, with the data of the node and references to its left and right child nodes. The
class defines the binary tree, with the root node being null initially. The
method inserts a new node into the binary tree, and the
method is used to recursively insert the node into the correct position in the binary tree.
method is used to perform post-order traversal on the binary tree. It takes in the starting node as a parameter and checks if the node is null. If it is not null, it calls itself recursively on the left subtree, then the right subtree, and finally, it logs the value of the current node.

Big O Complexity Analysis: The time complexity of the post-order traversal algorithm is O(n), where n is the number of nodes in the binary tree. This is because the algorithm visits every node in the binary tree once. The space complexity of the algorithm is also O(n), as the recursive calls of the
method create a call stack of size O(n). Therefore, the overall space used by the algorithm is proportional to the height of the binary tree, which can be at most O(n) for a completely unbalanced tree.