Implementation of Binary Tree Operation in C++

By Bharat Pandey

Hello Coders, Today we will discuss Binary Tree and its Operation. A binary tree is a non-linear data structure where each node has at most 2 children.

Binary Tree - A tree is a binary tree if its nodes have atmost 2 children. we can say a tree is a binary tree if its nodes have either no child, 1 child, or 2 child nodes. 

 

Some Properties Of a Binary Tree:

1. The maximum number of nodes in a binary tree of height 'h' is 2^h - 1. (example - in the above binary tree the height is 3 so the    maximum number of nodes is 7)

2. In a Binary Tree with N nodes, the minimum possible height is Log₂(N+1).

3. A binary tree is a non-linear data structure. it means we can traverse in multiple ways, unlike linear data structure where we perform traversing only one logical way.

Some Operation on Binary Tree:

Note: we Perform the operation on the above-given tree.

1. Binary tree Traversal: is performed in the following ways.

Inorder(Left, Root, Right): D B E A C F

Preorder(Root, Left, Right): A B D E C F

Postorder(Left, Right, Root): D E B F C A

Level order(we traverse tree level-wise): A B C D E F

Note: In source code to implement level-order traversal uses the concept of a queue. so please learn queue and implementation of STL queue.

2. Insertion in Binary Tree: Given a Binary Tree and a key. the task is to insert the key into the binary tree.

The idea is to do level order traversal and when we find a node whose left child or right child is empty. we add key at this node.

3. Deletion in Binary Tree: Given a binary tree and a key to be deleted. The task is to delete the key from the binary tree.

In order to delete a key from the binary tree. first, find the deepest and rightmost node in a binary tree and which node holds the key. then replace the deepest rightmost node's data with the node to be deleted. then delete the deepest rightmost node.

I think you understand the concept of the Binary tree but one question that comes to your mind is how to implement these operations.

So I will give the idea of how to create a binary tree in c++ Programming and I also upload full source code.

/* 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;
  Node(int data)
  {
    this->data = data;
    left = right = NULL;
  }
  
};

 Ok, GoodBye Coders. Hope you understand the Concept. if you find any mistake or error, please post in the reviews section.