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 2h - 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 Log2(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.
Submitted by Bharat Pandey (Techbharat)
Download packets of source code on Coders Packet
Comments