Binary Search Tree: Program to traverse using Postorder recursive approach

Write a program to display the Postorder Traversal of a Binary Search Tree (BST).
The Postorder of a Binary Search Tree is: left subtree, right subtree, root

Applications of Postorder Traversal

1. Postorder traversal is a very important concept in BST as it can be used to solve many Recursion and Dp-related Problems.
2. The Postorder traversal is mainly used to delete the tree.
3. Postorder traversal is also useful to get the postfix expression of a Binary Expression Tree.

Postorder recursive requires two functions

1. postOrder(): The function is used to call the postOrderCallback function and pass root as a parameter
2. postOrderCallback(node): The Main Recursive callback function which uses the below algorithm to traverse and
print the nodes in Postorder.

Algorithm

1. If the node is null, return from the function
2. Call the postOrderCallback function recursively with the left of the node as a parameter
3. Call the postOrderCallback function recursively with the right of the node as a parameter
4. Print the data of the node

Complexity

Time Complexity: O(N)
Auxiliary Space Complexity: O(Height of Tree)

The Time Complexity will be O(N) as visit every node once, and the space complexity will be O(Height of Tree)
which is O(logN) for a perfect binary tree, the Space Complexity is because of the stack memory
consumed by the recursive calls.

Java Code

  class BinarySearchTree {
        
        class Node {
          // Node class for Binary Search Tree
          int data;
          Node left, right;
        
          // Constructor to set the value of the node
          Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
          }
        }
        
        private Node root = null;
        
        // Function to print the postOrder traversal of the tree
        public void postOrder() {
          // postOrder traversal: left right root
          postOrderCallback(root);
        }
        
        public void postOrderCallback(Node node) {
          // If node is null return
          if (node == null) {
            return;
          }
        
          // Go to the left
          postOrderCallback(node.left);
        
          // Go to the right
          postOrderCallback(node.right);
        
          // Print the value of node
          System.out.print(node.data + " ");
        }
        
        // Insert array of num into the BST
        public void insertArray(int nums[]) {
          for (int i = 0; i < nums.length; i++) {
            insert(nums[i]);
          }
        }
        
        // Insert a value in BST Iteratively
        public void insert(int data) {
          // Check if root is null,
          // if null then create a node and make it root
          if (root == null) {
            root = new Node(data);
            return;
          }
        
          // Start traversing from the root and find the position of node to insert
          Node current = root;
          while (current != null) {
            if (data < current.data) {
              // Insert the node if the position is empty
              if (current.left == null) {
                current.left = new Node(data);
                return;
              }
              current = current.left;
            } else {
              if (current.right == null) {
                // Insert the node if the position is empty
                current.right = new Node(data);
                return;
              }
              current = current.right;
            }
          }
        }
        
        public static void main(String[] args) {
          int[] nums = { 8, 2, 6, 12, 11, 10 };
        
          BinarySearchTree bst = new BinarySearchTree();
          bst.insertArray(nums);
        
          // To check if postOrder is right:
          // Check that if the data is printed in ascending order
          System.out.print("Post Order traversal: ");
          bst.postOrder();
        }
        
   }

Output

Post Order traversal: 6 2 10 11 12 8