Given N elements to be inserted into Binary Search Tree. The task is to construct a binary search tree with only insert operation and finally print the elements in the postorder traversal. The BST is constructed according to the arrival order of elements.
Examples:
Input: N elements = {8, 5, 10, 3, 4, 9, 7}
Output: 4 3 7 5 9 10 8
For the above input, the BST is:
8
/ \
5 10
/ \ /
3 7 9
\
4
The post-order traversal of the above BST is 4 3 7 5 9 10 8
Approach: The approach to solve this problem is to construct the BST using insertion method in BST. Once all the nodes are inserted, print the postorder traversal of the tree.
Below is the implementation of the above approach:
C++
// C++ program to insert nodes// and print the postorder traversal#include <bits/stdc++.h>using namespace std;// structure to store the BSTstruct Node { int data; Node* left = NULL; Node* right = NULL;};// locates the memory spaceNode* newNode(int key){ Node* temp = new Node; temp->data = key; temp->left = NULL; temp->right = NULL; return temp;}// inserts node in the BSTNode* insertNode(Node* head, int key){ // if first node if (head == NULL) head = newNode(key); else { // move to left if (key < head->data) head->left = insertNode(head->left, key); // move to right else head->right = insertNode(head->right, key); } return head;}// print the postorder traversalvoid posOrder(Node* head){ // leaf node is null if (head == NULL) return; // left posOrder(head->left); // right posOrder(head->right); // data cout << head->data << " ";}// Driver Codeint main(){ Node* root = NULL; root = insertNode(root, 8); root = insertNode(root, 5); root = insertNode(root, 10); root = insertNode(root, 3); root = insertNode(root, 4); root = insertNode(root, 9); root = insertNode(root, 7); // prints the postorder traversal of // the tree posOrder(root); cout << endl;} |
Java
// Java program to insert nodes// and print the postorder traversalclass GFG { // structure to store the BST static class Node { int data; Node left = null; Node right = null; }; // locates the memory space static Node newNode(int key) { Node temp = new Node(); temp.data = key; temp.left = null; temp.right = null; return temp; } // inserts node in the BST static Node insertNode(Node head, int key) { // if first node if (head == null) head = newNode(key); else { // move to left if (key < head.data) head.left = insertNode(head.left, key); // move to right else head.right = insertNode(head.right, key); } return head; } // print the postorder traversal static void posOrder(Node head) { // leaf node is null if (head == null) return; // left posOrder(head.left); // right posOrder(head.right); // data System.out.print(head.data + " "); } // Driver Code public static void main(String[] args) { Node root = new Node(); root = insertNode(root, 8); root = insertNode(root, 5); root = insertNode(root, 10); root = insertNode(root, 3); root = insertNode(root, 4); root = insertNode(root, 9); root = insertNode(root, 7); // prints the postorder traversal of // the tree posOrder(root); System.out.println(""); }}// This code has been contributed by 29AjayKumar |
Python3
# Python program to insert nodes# and print the postorder traversalimport math# structure to store the BSTclass Node: def __init__(self,data): self.data = data self.left = None self.right=None# locates the memory spacedef newNode(key): temp = Node(key) temp.data = key temp.left = None temp.right = None return temp# inserts node in the BSTdef insertNode(head, key): # if first node if (head == None): head = newNode(key) else : # move to left if (key < head.data): head.left = insertNode(head.left, key) # move to right else: head.right = insertNode(head.right, key) return head# print the postorder traversaldef posOrder(head): # leaf node is None if (head == None): return # left posOrder(head.left) # right posOrder(head.right) # data print(head.data,end = " ")# Driver Codeif __name__=='__main__': root = None root = insertNode(root, 8) root = insertNode(root, 5) root = insertNode(root, 10) root = insertNode(root, 3) root = insertNode(root, 4) root = insertNode(root, 9) root = insertNode(root, 7) # prints the postorder traversal of # the tree posOrder(root)# This code is contributed by Srathore |
C#
// C# program to insert nodes// and print the postorder traversalusing System;class GFG { // structure to store the BST public class Node { public int data; public Node left = null; public Node right = null; }; // locates the memory space static Node newNode(int key) { Node temp = new Node(); temp.data = key; temp.left = null; temp.right = null; return temp; } // inserts node in the BST static Node insertNode(Node head, int key) { // if first node if (head == null) head = newNode(key); else { // move to left if (key < head.data) head.left = insertNode(head.left, key); // move to right else head.right = insertNode(head.right, key); } return head; } // print the postorder traversal static void posOrder(Node head) { // leaf node is null if (head == null) return; // left posOrder(head.left); // right posOrder(head.right); // data Console.Write(head.data + " "); } // Driver Code public static void Main(String[] args) { Node root = new Node(); root = insertNode(root, 8); root = insertNode(root, 5); root = insertNode(root, 10); root = insertNode(root, 3); root = insertNode(root, 4); root = insertNode(root, 9); root = insertNode(root, 7); // prints the postorder traversal of // the tree posOrder(root); Console.WriteLine(""); }}// This code contributed by Rajput-Ji |
Javascript
<script>// Javascript program to insert nodes// and print the postorder traversal// Structure to store the BSTclass Node { constructor() { this.data = 0; this.left = null; this.right = null; }};// Locates the memory spacefunction newNode(key){ var temp = new Node(); temp.data = key; temp.left = null; temp.right = null; return temp;}// Inserts node in the BSTfunction insertNode(head, key){ // If first node if (head == null) head = newNode(key); else { // Move to left if (key < head.data) head.left = insertNode(head.left, key); // Move to right else head.right = insertNode(head.right, key); } return head;}// Print the postorder traversalfunction posOrder(head){ // Leaf node is null if (head == null) return; // Left posOrder(head.left); // Right posOrder(head.right); // Data document.write(head.data + " ");}// Driver Codevar root = null;root = insertNode(root, 8);root = insertNode(root, 5);root = insertNode(root, 10);root = insertNode(root, 3);root = insertNode(root, 4);root = insertNode(root, 9);root = insertNode(root, 7);// Prints the postorder traversal of// the treeposOrder(root);document.write("<br>");// This code is contributed by rutvik_56</script> |
Output
4 3 7 5 9 10 8
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
