Binary Search Tree (BST)
Traversals – Inorder, Preorder, Post Order
Given a Binary Search Tree, The task is to print the elements in inorder, preorder,and
postorder traversal of the Binary Search Tree.
Input :
Output :
Inorder Traversal: 10 20 30 100 150 200 300
Preorder Traversal: 100 20 10 30 200 150 300
Postorder Traversal: 10 30 20 150 300 200 100.
Input :
Output :
Inorder Traversal: 8 12 20 22 25 30 40
Preorder Traversal: 22 12 8 20 30 25 40
Postorder Traversal: 8 20 12 25 40 30 22.
Below is the idea to solve the problem:
At first traverse left subtree then visit the root and then traverse the right subtree.
Follow the below steps to implement the idea:
Traverse left subtree
Visit the root and print the data.
Traverse the right subtree
The inorder traversal of the BST gives the values of the nodes in sorted order. To get the
decreasing order visit the right, root, and left subtree.
Below is the implementation of the inorder traversal.
// C program for different tree traversals
#include <stdio.h>
#include <stdlib.h>
// A binary tree node has data, pointer to left child
// and a pointer to right child
struct node {
int data;
struct node* left;
struct node* right;
};
// Helper function that allocates a new node with the
// given data and NULL left and right pointers.
struct node* newNode(int data)
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
// Given a binary tree, print its nodes in inorder
void printInorder(struct node* node)
if (node == NULL)
return;
// First recur on left child
printInorder(node->left);
// Then print the data of node
printf("%d ", node->data);
// Now recur on right child
printInorder(node->right);
// Driver code
int main()
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
// Function call
printf("Inorder traversal of binary tree is \n");
printInorder(root);
getchar();
return 0;
}
output :
Inorder traversal of binary tree is : 4 2 5 1 3
Time complexity: O(N), Where N is the number of nodes.
Auxiliary Space: O(h), Where h is the height of tree.
Below is the idea to solve the problem:
At first visit the root then traverse left subtree and then traverse the right subtree.
Follow the below steps to implement the idea :
Visit the root and print the data.
Traverse left subtree
Traverse the right subtree
Below is the implementation of the preorder traversal.
// C program for different tree traversals
#include <stdio.h>
#include <stdlib.h>
// A binary tree node has data, pointer to left child
// and a pointer to right child
struct node {
int data;
struct node* left;
struct node* right;
};
// Helper function that allocates a new node with the
// given data and NULL left and right pointers.
struct node* newNode(int data)
{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
// Given a binary tree, print its nodes in preorder
void printPreorder(struct node* node)
if (node == NULL)
return;
// First print data of node
printf("%d ", node->data);
// Then recur on left subtree
printPreorder(node->left);
// Now recur on right subtree
printPreorder(node->right);
// Driver code
int main()
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
// Function call
printf("Preorder traversal of binary tree is \n");
printPreorder(root);
getchar();
return 0;
Output :
Preorder traversal of binary tree is: 1 2 4 5 3
Time complexity: O(N), Where N is the number of nodes.
Auxiliary Space: O(H), Where H is the height of the tree.
Below is the idea to solve the problem:
At first traverse left subtree then traverse the right subtree and then visit the root.
Follow the below steps to implement the idea:
Traverse left subtree
Traverse the right subtree
Visit the root and print the data.
Below is the implementation of the postorder traversal:
// C program for different tree traversals
#include <stdio.h>
#include <stdlib.h>
// A binary tree node has data, pointer to left child
// and a pointer to right child
struct node {
int data;
struct node* left;
struct node* right;
};
// Helper function that allocates a new node with the
// given data and NULL left and right pointers.
struct node* newNode(int data)
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
// Given a binary tree, print its nodes according to the
// "bottom-up" postorder traversal.
void printPostorder(struct node* node)
if (node == NULL)
return;
// First recur on left subtree
printPostorder(node->left);
// Then recur on right subtree
printPostorder(node->right);
// Now deal with the node
printf("%d ", node->data);
// Driver code
int main()
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
// Function call
printf("Postorder traversal of binary tree is \n");
printPostorder(root);
getchar();
return 0;
Output :
Postorder traversal of binary tree is : 4 5 2 3 1
Time complexity: O(N), Where N is the number of nodes.
Auxiliary Space: O(H), Where H is the height of the tree
1.https://www.geeksforgeeks.org/check-if-given-inorder-and-preorder-traversals-are-valid-for-any-binary-tree-
without-building-the-tree/amp/
2. https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/amp/
3.https://www.geeksforgeeks.org/check-if-given-preorder-inorder-and-postorder-traversals-are-of-same-tree/amp/
4. https://www.geeksforgeeks.org/construct-tree-inorder-level-order-traversals-set-2/amp/
5. https://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-
traversals/amp/
6.https://www.geeksforgeeks.org/pre-order-post-order-and-in-order-traversal-of-a-binary-tree-in-one-traversal-
using-recursion/amp/
7.https://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/amp/?
8.https://www.geeksforgeeks.org/leaf-nodes-preorder-binary-search-treeusing-recursion/amp/
9.https://www.geeksforgeeks.org/leaf-nodes-preorder-binary-search-treeusing-recursion/amp/
10.https://www.geeksforgeeks.org/maximum-sub-tree-sum-in-a-binary-tree-such-that-the-sub-tree-is-also-a-
bst/amp/
