by A Binary tree is a tree in which any node can have at max 2 nodes which are known as left subtree and right subtree. If each node of a binary tree contains Zero or Two nodes then this binary tree is known as proper binary tree else it will be called improper binary tree.
Typically a binary tree can be shown as follows:
As shown in above diagram “Software” is the Root node whose left child is “Trial Version” and right child is “Paid Version”.
A Binary Tree can be defined as follows:
// Struct definition of Binary Tree
struct BinaryTree
{
int data;
BinaryTree* left;
BinaryTree* right;
};
Traversing a Tree:
Accessing or visiting each and every node of a tree is known as traversal of a tree.
Basically there are three kind of traversal mechanism:
1) Preorder traversal(root, left, right):
In this kind of traversal root/parent node is traversed first and then its left and right childrens. So for above shown picture preorder traversal would be as follows:
Software, Trial Version, Student Copy, Home Copy, Paid Version, Commercial Version, Enterprise Version.
2) Postorder traversal(left, right, root):
In this kind of traversal root/parent node is traversed after all its children are traversed. So for above shown picture postorder traversal would be as follows:
Student Copy, Home Copy, Trial Version, Commercial Version, Enterprise Version, Paid Version, Software.
3) Inorder traversal(left, root, right):
In this kind of traversal first left child then parent node and right child are traversed. So for above shown picture inorder traversal would be as follows:
Student Copy, Trial Version, Home Copy, Software, Commercial Version, Paid Version, Enterprise Version.
Now that we understood basic concept of Binary Tree, let’s have a look on below binary tree structure as shown in below image.
Now lets have a look at the basic code to create above shown binary tree.
// Create binary tree and returns root node
BinaryTree* createRandomBinaryTree()
{
BinaryTree* root = new BinaryTree;
root->data = 10;
root->left = NULL;
root->right = NULL;
// Adding 2 nodes(2,4) as left and right child of root
BinaryTree* temp = new BinaryTree();
temp->data = 2;
temp->left = NULL;
temp->right = NULL;
root->left = temp;
//Create next node (4)
temp = new BinaryTree();
temp->data = 4;
temp->left = NULL;
temp->right = NULL;
root->right = temp;
//Create next node (7) as left child of (2)
temp = new BinaryTree();
temp->data = 7;
temp->left = NULL;
temp->right = NULL;
root->left->left = temp;
// Create next node (8) as right child of (4)
temp = new BinaryTree();
temp->data = 8;
temp->left = NULL;
temp->right = NULL;
root->right->right = temp;
return root;
}
Preorder traversal of above shown tree would be as follows:
10, 2, 7, 4, 8.
Now let’s have a look at the code for preorder traversal of a tree.
// Function to preorder traversal. Root Node MUST be passed to this function
void preOrderBinaryTree(BinaryTree* node)
{
cout << "Preorder Node Data is : " << node->data << endl;
if (node->left)
{
preOrderBinaryTree(node->left);
}
if (node->right)
{
preOrderBinaryTree(node->right);
}
}
Postorder traversal of above shown tree would be as follows:
7, 2, 8, 4, 10.
Now let’s have a look at the code for postorder traversal of a tree.
// Function to postorder traversal. Root Node MUST be passed to this function
void postOrderBinaryTree(BinaryTree* node)
{
if (node->left)
{
postOrderBinaryTree(node->left);
}
if (node->right)
{
postOrderBinaryTree(node->right);
}
cout << "Postorder Node Data is : " << node->data << endl;
}
Inorder traversal of above shown tree would be as follows:
7, 2, 10, 4, 8.
Now let’s have a look at the code for inorder traversal of a tree.
// Function to inorder traversal. Root Node MUST be passed to this function
void inOrderBinaryTree(BinaryTree* node)
{
if (node->left)
{
inOrderBinaryTree(node->left);
}
cout << "Inorder Node Data is : " << node->data << endl;
if (node->right)
{
inOrderBinaryTree(node->right);
}
}
For deleting this entire tree, we can write some function which uses any of the above mentioned traversal technique as shown below:
// Function to delete binary tree. Root Node MUST be passed to this function
void deleteBinaryTree(BinaryTree* node)
{
if (node->left)
{
deleteBinaryTree(node->left);
}
if (node->right)
{
deleteBinaryTree(node->right);
}
cout << "Deleting Node Data is : " << node->data << endl;
delete node;
}
Now, let’s have a look at the sample main function which uses all the above functions:
int main()
{
BinaryTree* root;
root = createRandomBinaryTree();
preOrderBinaryTree(root);
inOrderBinaryTree(root);
postOrderBinaryTree(root);
deleteBinaryTree(root);
cout << "All Node data printed" << endl;
}
Output of above program is as follows:
Preorder Node Data is : 10 Preorder Node Data is : 2 Preorder Node Data is : 7 Preorder Node Data is : 4 Preorder Node Data is : 8 Inorder Node Data is : 7 Inorder Node Data is : 2 Inorder Node Data is : 10 Inorder Node Data is : 4 Inorder Node Data is : 8 Postorder Node Data is : 7 Postorder Node Data is : 2 Postorder Node Data is : 8 Postorder Node Data is : 4 Postorder Node Data is : 10 Deleting Node Data is : 7 Deleting Node Data is : 2 Deleting Node Data is : 8 Deleting Node Data is : 4 Deleting Node Data is : 10 All Node data printed
