A Binary Tree is a form of Tree Data Structure with almost two children for every node. This is required to store the data in a hierarchical form, unlike linear data structures.
1. Introduction
A simple Binary Tree is not useful for real-time applications, but it is a foundation to implement the other trees such as Binary Search Tree, AVL Tree, Red-Black Tree, and Splay Tree. However, the sample implementation provided in this article is useful for the educative purpose.
Representation
- Root: The topmost node.
- Node: Node consists of Data, Left and Right pointers.
- Left: Pointer to the left child.
- Right: Pointer to the right child.
// Binary Tree node representation struct Node { int data; // Actual data Node* left; // Pointer to left child Node* right; // Pointer to right child // Node constructor Node(int d) : data(d), left(NULL), right(NULL) {} }; // The root node Node* root;
Applications
- A simple Binary Tree is not useful for real-time applications, because of its Time Complexity. Since the data elements are not sorted in a particular order, the search, insertion, and deletion operations work in O(n) time.
- However, it is used to implement the other forms of Binary Trees useful for applications. This includes Binary Search Tree, AVL Tree, Red-Black Tree, Splay Tree, and Heaps.
2. Insertion on Binary Tree
In a Binary Tree, a new node is inserted at the last position. The position can be identified by traversing the tree in level order. We find a node with either its Left or Right child empty and insert a new node.
Algorithm
- Create the new Node with the data and initialize its Left and Right child to NULL.
- Traverse the tree in Levelorder (10, 20, 30, 40, 50 in the above tree).
- Find the first node with either its Left or Right child is free.
- Link the new node to the free position.
Code
// Insert a node in the deepest location Node* BinaryTree::insert(int data) { // Check if the tree is empty. If so, insert the node at the root. if (root == NULL) { root = new Node(data); return root; } // Traverse the tree in level order to insert in the deepest location. std::queue<Node*> q; q.push(root); while (! q.empty()) { Node* p = q.front(); q.pop(); if (p->left == NULL) { p->left = new Node(data); return p->left; } else { q.push(p->left); } if (p->right == NULL) { p->right = new Node(data); return p->right; } else { q.push(p->left); } } }
Examples
Here are the examples of inserting the data 10, 20, 30, 40, and 50 in a Binary Tree.
1. Insert the first node (10)
2. Insert node (20) into the Binary Tree
3. Binary Tree after inserting node (30)
4. After inserting node (40)
5. After inserting node (50)
3. Deletion on Binary Tree
A node can not be deleted straight away from the tree because it may have children. So, the easiest way is to replace the node’s data with the deepest node. Finally, delete the deepest node as it does not have any children.
Algorithm
- Check the tree is empty and return if true
- Check the tree has only a single node and matches the given data. If true, delete the node, set the root to NULL, and return.
- Otherwise, traverse the tree in Levelorder starting from the root node.
- Search the target node that contains the given data.
- Continue the traversal to locate the deepest node.
- Replace the target node with the deepest node’s data.
- Delete the deepest node.
Code
/ Delete the node by the given data void BinaryTree::remove(int data) { // Check the tree is empty and return if true if (root == NULL) { return; } // Check the tree has only a single node. if (root->left == NULL && root->right == NULL) { // Check if the root node matches the given data. if (root->data == data) { // Delete the root node delete root; root = NULL; } return; } Node *target = NULL; // Node requested for deletion Node* p = NULL; // Last node of the tree Node *pp = NULL; // Parent of last node // Traverse the tree in level order std::queue<Node*> q; q.push(root); while (! q.empty()) { p = q.front(); q.pop(); if (p->data == data) { // Found the target node, proceed to find the last node target = p; } if (p->left != NULL) { pp = p; q.push(p->left); } if (p->right != NULL) { pp = p; q.push(p->right); } } // Replace the target node with the last node's data and delete the last node if (target != NULL) { target->data = p->data; if (pp->left == p) { pp->left = NULL; } else { pp->right = NULL; } delete p; } }
Examples
1. Delete node (20) from the Binary Tree
2. Delete node (10)
4. Search on Binary Tree
Searching the data in Binary Tree can be made simple using recursive calls. Start the search from the root node, search the left subtree, and search the right subtree. This process can be repeated for every node until the node is found.
Algorithm
- Check if the tree is empty and return NULL.
- Check if the current node matches the data and return the node if true.
- Perform the recursive call to search on the left subtree and return the node if found.
- Perform the recursive call to search on the right subtree and return the node if found.
Code
// Search the node by the given data Node* BinaryTree::search(int data, Node* root) { // Check if the tree is empty and return if (root == NULL) { return NULL; } // Check if the current node matches the data and return the node if true. if (root->data == data) { return root; } // Search on the left sub tree and return the node if found. Node* target = search(data, root->left); if (target != NULL) { return target; } // Search on the right sub tree and return the node if found. target = search(data, root->right); return target; }
5. Traversals on Binary Tree
A Binary Tree can be traversed in any one of the following orders.
- Preorder (Root, Left, Right)
- Postorder (Left, Right, Root)
- Inorder (Left, Root, Right)
- Levelorder (Level 0, Level 1, and so on.)
- Preorder: 10, 20. 40, 50, 30
- Postorder: 40, 50, 20, 30, 10
- Inorder: 40, 20, 50, 10, 30
- Levelorder: 10, 20, 30, 40, 50
5.1 Preorder Traversal
Traverse the tree in the order of Root, left, and right subtree.
// Traverse the tree in preorder (parent, left, right) void BinaryTree::traverse_preorder(Node* p) { if (p != NULL) { cout << p->data << endl; traverse_preorder(p->left); traverse_preorder(p->right); } }
5.2 Postorder Traversal
Traverse the tree in the order of left subtree, right subtree, and Root node.
// Traverse the tree in postorder (left, right, parent) void BinaryTree::traverse_postorder(Node* p) { if (p != NULL) { traverse_postorder(p->left); traverse_postorder(p->right); cout << p->data << endl; } }
5.3 Inorder Traversal
Traverse the tree in the order of the left subtree, the Root node, and the right subtree.
// Traverse the tree inorder (left, parent, right) void BinaryTree::traverse_inorder(Node* p) { if (p != NULL) { traverse_inorder(p->left); cout << p->data << endl; traverse_inorder(p->right); } }
5.4 Levelorder Traversal
Traverse the tree in the breadth-first approach. The std::queue data structure is used here to traverse the tree in the order of level 0, level 1, and so on.
// Traverse the tree in level order (breadth first) void BinaryTree::traverse_levelorder(Node* p) { if (p == NULL) { return; } // Start the traversal from root node std::queue<Node*> q; q.push(root); while (! q.empty()) { Node* p = q.front(); q.pop(); // Visit the current node cout << p->data << endl; // Enqueue the left and right child to process in order. if (p->left != NULL) { q.push(p->left); } if (p->right != NULL) { q.push(p->right); } } }
6. Implementation of Binary Tree in C++
/** * C++ example to demonstrate the Binary Tree */ #include <iostream> #include <queue> using namespace std; // Binary Tree node representation struct Node { int data; // Actual data Node* left; // Pointer to left child Node* right; // Pointer to right child // Node constructor Node(int d) : data(d), left(NULL), right(NULL) {} }; /** * Binary Tree implementation */ class BinaryTree { // The root node Node* root; public: // Constructor BinaryTree() : root(NULL) {} // Get the root node Node* get_root() { return root; } // Insert a node in the deepest location // Returns the node inserted Node* insert(int data); // Delete the node by the given data void remove(int data); // Search the node by the given data Node* search(int data, Node* root); // Preorder traversal void traverse_preorder(Node* p); // Postorder traversal void traverse_postorder(Node* p); // Inorder traversal void traverse_inorder(Node* p); // Levelorder traversal void traverse_levelorder(Node* p); }; // Insert a node in the deepest location Node* BinaryTree::insert(int data) { // Check if the tree is empty. If so, insert the node at the root. if (root == NULL) { root = new Node(data); return root; } // Traverse the tree in level order to insert in the deepest location. std::queue<Node*> q; q.push(root); while (! q.empty()) { Node* p = q.front(); q.pop(); if (p->left == NULL) { p->left = new Node(data); return p->left; } else { q.push(p->left); } if (p->right == NULL) { p->right = new Node(data); return p->right; } else { q.push(p->left); } } } // Delete the node by the given data void BinaryTree::remove(int data) { // Check the tree is empty and return if true if (root == NULL) { return; } // Check the tree has only a single node. if (root->left == NULL && root->right == NULL) { // Check if the root node matches the given data. if (root->data == data) { // Delete the root node delete root; root = NULL; } return; } Node *target = NULL; // Node requested for deletion Node* p = NULL; // Last node of the tree Node *pp = NULL; // Parent of last node // Traverse the tree in level order std::queue<Node*> q; q.push(root); while (! q.empty()) { p = q.front(); q.pop(); if (p->data == data) { // Found the target node, proceed to find the last node target = p; } if (p->left != NULL) { pp = p; q.push(p->left); } if (p->right != NULL) { pp = p; q.push(p->right); } } // Replace the target node with the last node's data and delete the last node if (target != NULL) { target->data = p->data; if (pp->left == p) { pp->left = NULL; } else { pp->right = NULL; } delete p; } } // Search the node by the given data Node* BinaryTree::search(int data, Node* root) { // Check if the tree is empty and return if (root == NULL) { return NULL; } // Check if the current node matches the data and return the node if true. if (root->data == data) { return root; } // Search on the left sub tree and return the node if found. Node* target = search(data, root->left); if (target != NULL) { return target; } // Search on the right sub tree and return the node if found. target = search(data, root->right); return target; } // Traverse the tree in preorder (parent, left, right) void BinaryTree::traverse_preorder(Node* p) { if (p != NULL) { cout << p->data << endl; traverse_preorder(p->left); traverse_preorder(p->right); } } // Traverse the tree in postorder (left, right, parent) void BinaryTree::traverse_postorder(Node* p) { if (p != NULL) { traverse_postorder(p->left); traverse_postorder(p->right); cout << p->data << endl; } } // Traverse the tree inorder (left, parent, right) void BinaryTree::traverse_inorder(Node* p) { if (p != NULL) { traverse_inorder(p->left); cout << p->data << endl; traverse_inorder(p->right); } } // Traverse the tree in level order (breadth first) void BinaryTree::traverse_levelorder(Node* p) { if (p == NULL) { return; } // Start the traversal from root node std::queue<Node*> q; q.push(root); while (! q.empty()) { Node* p = q.front(); q.pop(); // Visit the current node cout << p->data << endl; // Enqueue the left and right child to process in order. if (p->left != NULL) { q.push(p->left); } if (p->right != NULL) { q.push(p->right); } } } int main() { /** Create a binary tree and insert data * 10 * / \ * 20 30 * / \ * 40 50 */ BinaryTree tree; tree.insert(10); tree.insert(20); tree.insert(30); tree.insert(40); tree.insert(50); // Search Node* p = tree.search(30, tree.get_root()); cout << "Search(30) located node: " << p->data << endl; // Traversals cout << "Binary Tree preorder traversal" << endl; tree.traverse_preorder(tree.get_root()); cout << "Binary Tree inorder traversal" << endl; tree.traverse_inorder(tree.get_root()); cout << "Binary Tree postorder traversal" << endl; tree.traverse_postorder(tree.get_root()); cout << "Binary Tree level order traversal" << endl; tree.traverse_levelorder(tree.get_root()); // Delete data tree.remove(20); tree.remove(10); cout << "Binary Tree level order traversal" << endl; tree.traverse_levelorder(tree.get_root()); }
Output
Search(30) located node: 30
Binary Tree preorder traversal
10
20
40
50
30
Binary Tree inorder traversal
40
20
50
10
30
Binary Tree postorder traversal
40
50
20
30
10
Binary Tree level order traversal
10
20
30
40
50
Binary Tree level order traversal
40
50
30