Postorder Traversal

Mark as Completed

Lesson

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:

Input:
    50
   /  \
  25  125
 / \   / \
20 30 60  70
    /    /  \
   33   40  90

Output:
20 30 25 33 40 30 60 90 70 125 50

Walkthrough

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) {
      return;
    }
    this.postOrder(node.left);
    this.postOrder(node.right);
    console.log(node.data);
  }
}

The Node
class defines a node in the binary tree, with the data of the node and references to its left and right child nodes. The BinaryTree
class defines the binary tree, with the root node being null initially. The insert
method inserts a new node into the binary tree, and the insertNode
method is used to recursively insert the node into the correct position in the binary tree.The postOrder
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 postOrder
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.

Previous Lesson Next Lesson