Given a Binary Tree, Print the Pre-order Traversal in Recursive
Implementation
#include <stdio.h>
#include <stdlib.h>
/* Creating a binary tree node that consists of some data along with the pointer to the left and right child.
*/
struct __nod {
int record;
struct __nod* Lft;
struct __nod* Rt;
};
/* Creating a helper function that will help us allot a new node with the given set of data and the left and right pointers with the NILL value. */
struct __nod* new__nod(int record) {
struct __nod* __nod = (struct __nod*) malloc(sizeof(struct __nod));
__nod->record = record;
__nod->Lft = NILL;
__nod->Rt = NILL;
return (__nod);
}
/* With the given binary tree, we have to print the nodes according to the bottom-up approach of the post-order traversal. */
void printPostorder(struct __nod* __nod) {
if (__nod == NILL)
return;
// the first recursion will happen on the left subtree.
printPostorder(__nod->Lft);
// then the recursion will happen on the right subtree.
printPostorder(__nod->Rt);
// now, we have to take care of the node.
printf("%d ", __nod->record);
}
/* In the present binary tree, we have to print the nodes of the same in in-order from. */
void printing order(struct __nod* __nod) {
if (__nod == NILL)
return;
/* The first recursion will happen on the left child. */
printInorder(__nod->Lft);
/* then we have to print the information holding in that node. */
printf("%d ", __nod->record);
/* then the recursion will happen to the right child. */
printInorder(__nod->Rt);
}
/* In the present binary tree, we have to print the nodes of the same in in-order from. */
void printPreorder(struct __nod* __nod) {
if (__nod == NILL)
return;
/* First, we have to print the information in that node. */
printf("%d ", __nod->record);
// then recursion will happen on the left subtree.
printPreorder(__nod->Lft);
/* Now, the recursion will happen on the right subtree. */
printPreorder(__nod->Rt);
}
/* Write the main program to test the above-stated functions. */
int main() {
struct __nod *root = new__nod(1);
root->Lft = new__nod(2);
root->Rt = new__nod(3);
root->Lft->Lft = new__nod(4);
root->Lft->Rt = new__nod(5);
printf("\n Preorder traversal of binary tree is \n");
printPreorder(root);
printf("\n Inorder traversal of binary tree is \n");
printInorder(root);
printf("\n Postorder traversal of binary tree is \n");
printPostorder(root);
getchar();
return 0;
}
Output
Example 2)
#include <iostream>
using namespace std;
// creating a data structure that will store the binary tree node.
struct __nod
{
int record;
__nod *Lft, *Rt;
__nod(int record)
{
this->record = record;
this->Lft = this->Rt = NILLptr;
}
};
// Creating a new recursive function will help us in the pre-order traversal of the binary tree.
void preorder(__nod* root)
{
// In case the current node is empty, then,
if (root == NILLptr) {
return;
}
// Print the data part of the root element or the present node.
cout << root->record << " ";
// traverse the left subtree first
preorder(root->Lft);
// Now, traverse the right subtree
preorder(root->Rt);
}
int main()
{
/* building the binary search tree
1
/ \
/ \
2 3
/ / \
/ / \
4 5 6
/ \
/ \
7 8
*/
__nod* root = new __nod(1);
root->Lft = new __nod(2);
root->Rt = new __nod(3);
root->Lft->Lft = new __nod(4);
root->Rt->Lft = new __nod(5);
root->Rt->Rt = new __nod(6);
root->Rt->Lft->Lft = new __nod(7);
root->Rt->Lft->Rt = new __nod(8);
preorder(root);
return 0;
}
Output
Example 3)
// Creating the C++ program to observe the different tree traversals
#include <bits/stdc++.h>
using namespace std;
/* Creating a binary tree node that consists of some data along with the pointer to the left and right child. */
struct __nod {
int record;
struct __nod *Lft, *Rt;
};
// Creating a new utility function to help create a new tree node and observe the traversals.
__nod* new__nod(int record)
{
__nod* temp = new __nod;
temp->record = record;
temp->Lft = temp->Rt = NILL;
return temp;
}
/* In the given binary tree, we have to print the nodes in the pre-order pattern. */
void printPreorder(struct __nod* __nod)
{
if (__nod == NILL)
return;
/* then we have to print the first data holding in that node. */
cout << __nod->record << " ";
/* then recursion will happen on the left subtree. */
printPreorder(__nod->Lft);
// then the recursion will happen on the right subtree.
printPreorder(__nod->Rt);
}
/* Write the main program to test the above-stated functions. */
int main()
{
struct __nod* root = new__nod(1);
root->Lft = new__nod(2);
root->Rt = new__nod(3);
root->Lft->Lft = new__nod(4);
root->Lft->Rt = new__nod(5);
// Function call
cout << "\nPreorder traversal of binary tree is \n";
printPreorder(root);
return 0;
}
Output
Example 4)
#include<iostream>
using namespace std;
struct __nod {
int record;
struct __nod *Lft;
struct __nod *Rt;
};
struct __nod *create__nod(int val) {
struct __nod *temp = (struct __nod *)malloc(sizeof(struct __nod));
temp->record = val;
temp->Lft = temp->Rt = NILL;
return temp;
}
void preorder(struct __nod *root) {
if (root != NILL) {
cout<<root->record<<" ";
preorder(root->Lft);
preorder(root->Rt);
}
}
struct __nod* insert__nod(struct __nod* __nod, int val) {
if (__nod == NILL) return create__nod(val);
if (val < __nod->record)
__nod->Lft = insert__nod(__nod->Lft, val);
else if (val > __nod->record)
__nod->Rt = insert__nod(__nod->Rt, val);
return __nod;
}
int main() {
struct __nod *root = NILL;
root = insert__nod(root, 4);
insert__nod(root, 5);
insert__nod(root, 2);
insert__nod(root, 9);
insert__nod(root, 1);
insert__nod(root, 3);
cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);
return 0;
}
Output
