Introduction to Trees & Basic Terminologies (Data Structures)
Last Updated on: 17th Jan 2026 23:17:49 PM
A Tree is one of the most powerful and widely used non-linear data structures in computer science. Unlike linear data structures such as arrays, stacks, and queues, a tree organizes data in a hierarchical structure. This structure helps represent relationships between elements in a natural and efficient way.
Trees are used in many real-world applications such as file systems, databases, artificial intelligence, networking, and compiler design. Understanding trees and their basic terminologies is essential for learning advanced data structures and algorithms.
Example
#include<iostream>
#include<queue>
using namespace std;
class Node
{
public:
int data;
Node* left,*right;
Node(int value)
{
data = value;
left=right=NULL;
}
};
int main()
{
int x ;
int first, second;
cout<<"Enter the root element : ";
cin>>x;
queue<Node*>q;
Node *root = new Node(x);
q.push(root);
// build the binary tree
while(!q.empty())
{
Node *temp= q.front();
q.pop();
cout<<"ENter the left value of "<<temp->data<<" : ";
cin>>first;
// left node
if(first!=-1)
{
temp->left= new Node(first);
q.push(temp->left);
}
// right node
cout<<"ENter the Right value of "<<temp->data<<" : ";
cin>>second;
if(second!=-1)
{
temp->right= new Node(second);
q.push(temp->right);
}
}
return 0;
}
Sample Example
Enter the root element : 1
ENter the left value of 1 : 2
ENter the Right value of 1 : 3
ENter the left value of 2 : 4
ENter the Right value of 2 : 5
ENter the left value of 3 : 6
ENter the Right value of 3 : 7
ENter the left value of 4 : -1
ENter the Right value of 4 : -1
ENter the left value of 5 : -1
ENter the Right value of 5 : -1
ENter the left value of 6 : -1
ENter the Right value of 6 : -1
ENter the left value of 7 : 8
ENter the Right value of 7 : -1
ENter the left value of 8 : -1
ENter the Right value of 8 : -1
Another way to create Binary tree
Example
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *left,*right;
Node(int value)
{
data = value;
left=right=NULL;
}
};
Node *BinaryTree()
{
int x;
cin>>x;
if(x==-1)
{
return NULL;
}
Node *temp = new Node(x);
// left side create
cout<<"Enter the left child of "<<x<<" : ";
temp->left= BinaryTree();
// right side create
cout<<"Enter the right child of "<<x<<" : ";
temp->right= BinaryTree();
return temp;
}
int main()
{
cout<<"Enter the Root Node ";
Node *root;
root= BinaryTree();
return 0;
}
Sample Execution
Enter the Root Node 1
Enter the left child of 1 : 2
Enter the left child of 2 : 3
Enter the left child of 3 : 4
Enter the left child of 4 : -1
Enter the right child of 4 : -1
Enter the right child of 3 : 5
Enter the left child of 5 : -1
Enter the right child of 5 : -1
Enter the right child of 2 : 6
Enter the left child of 6 : -1
Enter the right child of 6 : -1
Enter the right child of 1 : 7
Enter the left child of 7 : -1
Enter the right child of 7 : 8
Enter the left child of 8 : 9
Enter the left child of 9 : -1
Enter the right child of 9 : -1
Enter the right child of 8 : 10
Enter the left child of 10 : -1
Enter the right child of 10 : -1
Complte Program with Traverse
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *left,*right;
Node(int value)
{
data = value;
left=right=NULL;
}
};
Node *BinaryTree()
{
int x;
cin>>x;
if(x==-1)
{
return NULL;
}
Node *temp = new Node(x);
// left side create
cout<<"Enter the left child of "<<x<<" : ";
temp->left= BinaryTree();
// right side create
cout<<"Enter the right child of "<<x<<" : ";
temp->right= BinaryTree();
return temp;
}
void PreOrder(Node *root)
{
if(root ==NULL)
{
return;
}
//Node
cout<<root->data<<" ";
//Left
PreOrder(root->left);
//Right
PreOrder(root->right);
}
void InOrder(Node *root)
{
if(root ==NULL)
{
return;
}
//Left
InOrder(root->left);
//Node
cout<<root->data<<" ";
//Right
InOrder(root->right);
}
void PostOrder(Node *root)
{
if(root ==NULL)
{
return;
}
//Left
PostOrder(root->left);
//Right
PostOrder(root->right);
//Node
cout<<root->data<<" ";
}
int main()
{
// Tree creation Code
cout<<"Enter the Root Node ";
Node *root;
root= BinaryTree();
// PreOrder Print
cout<<"PreOrder :";
PreOrder(root);
// InOrder Print
cout<<"\nInOrder :";
InOrder(root);
// PostOrder Printf
cout<<"\nPostOrder :";
PostOrder(root);
return 0;
}
Sample OutPut
Enter the Root Node 1
Enter the left child of 1 : 2
Enter the left child of 2 : 3
Enter the left child of 3 : 4
Enter the left child of 4 : -1
Enter the right child of 4 : -1
Enter the right child of 3 : 5
Enter the left child of 5 : -1
Enter the right child of 5 : -1
Enter the right child of 2 : 6
Enter the left child of 6 : -1
Enter the right child of 6 : -1
Enter the right child of 1 : 7
Enter the left child of 7 : -1
Enter the right child of 7 : 8
Enter the left child of 8 : 9
Enter the left child of 9 : -1
Enter the right child of 9 : -1
Enter the right child of 8 : 10
Enter the left child of 10 : -1
Enter the right child of 10 : -1
PreOrder :1 2 3 4 5 6 7 8 9 10
InOrder :4 3 5 2 6 1 7 9 8 10
PostOrder :4 5 3 6 2 9 10 8 7 1
Binary Search Tree
Binary search tree creation and traverse
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *left,*right;
Node(int value){
data=value;
left=right=NULL;
}
};
Node * insert(Node *root, int target)
{
// base case
if(!root)
{
Node *temp = new Node(target);
return temp;
}
if(target<root->data) // left side
root->left=insert(root->left,target);
else
root->right=insert(root->right,target);
return root;
}
void inorder(Node *root)
{
if(!root)
return;
//left side
inorder(root->left);
//node
cout<<root->data<<" ";
//Right side
inorder(root->right);
}
int main() {
int arr[]={6,3,17,5,11,18,2,1,20,14};
Node *root=NULL;
for(int i=0;i<10;i++)
root=insert(root,arr[i]);
// traverse
inorder(root);
return 0;
}
Sample Output
1 2 3 5 6 11 14 17 18 20
Search element in binary search tree
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *left,*right;
Node(int value){
data=value;
left=right=NULL;
}
};
Node * insert(Node *root, int target)
{
// base case
if(!root)
{
Node *temp = new Node(target);
return temp;
}
if(target<root->data) // left side
root->left=insert(root->left,target);
else
root->right=insert(root->right,target);
return root;
}
void inorder(Node *root)
{
if(!root)
return;
//left side
inorder(root->left);
//node
cout<<root->data<<" ";
//Right side
inorder(root->right);
}
bool search(Node *root,int target)
{
if(!root)
{
return 0;
}
if(root->data==target)
{
return 1;
}
if(root->data>target)
{
return search(root->left,target);
}
else
{
return search(root->right,target);
}
}
int main() {
int arr[]={6,3,17,5,11,18,2,1,20,14};
Node *root=NULL;
for(int i=0;i<10;i++)
root=insert(root,arr[i]);
cout<<search(root,11)<<endl;
// traverse
// inorder(root);
return 0;
}