However, there’s another binary tree that is used most frequently and has several use cases. It’s called the Binary Search Tree (BST). This tree can make the search algorithm way faster, precisely log(n) time complexity. In the data structure, n means the number of nodes in the binary tree.

What are the Differences Between Binary Tree and Binary Search Tree?

The difference between the BST and regular Binary tree is in the BST left node has a smaller value than the root node, and the right node has a larger value than the root node. So, the left subtree will always contain a smaller value than the root, and the right subtree will always contain a larger value than the root.

In this Algorithm tutorial, you will learn:

What is a Binary Tree? What are the Differences Between Binary Tree and Binary Search Tree? Example of Binary Search Trees Types of Binary Tree Implementation of Binary Tree in C and C++: Implementation of Binary Tree in Python Application of Binary Tree

Example of Binary Search Trees

Let’s have the following example for demonstrating the concepts of the Binary Search Tree.

Here you can all the nodes follow the given discipline. There’s a formula for the maximum number of nodes in the Binary Search Tree. If we observe the above tree, we can see each node has two children except all the leaf nodes. And the height(h) of the given Binary Tree is 4. The formula is 2h – 1. So, it gives 15.

The above given image is not a complete Binary Tree or Balanced Binary Tree, is called the Complete Binary tree or Balanced Binary Tree. There’s another Data Structure called AVL (another type of Binary Tree) that optimizes the height of Binary Tree and performs search faster for the BST like in Fig 3. Try to calculate the in-order traversal of the Binary Tree given above. You’ll find that it will give a non-decreasing sorted array, and Traversal algorithms will be the same as the Binary Tree.

Types of Binary Tree:

Here are some important types of Binary Tree:

Full Binary Tree: Each node can have 0 or 2 child nodes in this binary tree. Only one child node is not allowed in this type of binary tree. So, except for the leaf node, all nodes will have 2 children.

Full Binary Tree: Each node can have 0 or 2 nodes. It seems like the Full Binary Tree, but all the leaf elements are lean to the left subtree, whereas in the full binary tree node can be in the right or left subtree.

Perfect Binary Tree: All the nodes must have 0 or 2 nodes, and all the leaf nodes should be at the same level or height. The above example of a full binary tree structure is not a Perfect Binary Tree because node 6 and node 1,2,3 are not in the same height. But the example of the Complete Binary Tree is a perfect binary tree.

Degenerate Binary Tree: Every node can have only a single child. All the operations like searching, inserting, and deleting take O(N) time.

Balanced Binary Tree: Here this binary tree, the height difference of left and right subtree is at most 1. So, while adding or deleting a node, we need to balance the tree’s height again. This type of Self-Balanced Binary Tree is called the AVL tree.

There are three basic operations of BST. Those are discussed in detail below.

Implementation of Binary Tree in C and C++:

#include #include <bits/stdc++.h> using namespace std; struct Node { int value; struct Node *left, *right; } struct Node *getEmptynode(int val) { struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node)); tempNode->value = val; tempNode->left = NULL; tempNode->right = NULL; return tempNode; } struct Node *successor(struct Node *node) { struct Node *present = node; // going to the left most node while (present != NULL && present->left != NULL) { present = present->left; } return present; } struct Node *insert(struct Node *node, int value) { if (node == NULL) { return getEmptynode(value); } if (value < node->value) { node->left = insert(node->left, value); } else { node->right = insert(node->right, value); } return node; } int searchInBST(struct Node *node, int value) { struct Node *current = node; while (current->value != value) { if (current->value > value) { current = current->left; } else { current = current->right; } if (current == NULL) { return 0; } } return 1; } void inorder(struct Node *root) { if (root != NULL) { inorder(root->left); cout « root->value « " “; inorder(root->right); } } struct Node *deleteNode(struct Node *node, int value) { if (node == NULL) { return node; } if (value < node->value) { node->left = deleteNode(node->left, value); } else if (value > node->value) { node->right = deleteNode(node->right, value); } else { if (node->left == NULL) { struct Node *temp = node->right; free(node); return temp; } else if (node->right == NULL) { struct Node *temp = node->left; free(node); return temp; } struct Node *temp = successor(node->right); node->value = temp->value; node->right = deleteNode(node->right, temp->value); } return node; } int main() { struct Node *root = NULL; root = insert(root, 8); root = insert(root, 4); root = insert(root, 12); root = insert(root, 2); root = insert(root, 6); root = insert(root, 10); root = insert(root, 14); root = insert(root, 1); root = insert(root, 3); root = insert(root, 5); root = insert(root, 7); root = insert(root, 9); root = insert(root, 11); root = insert(root, 13); root = insert(root, 15);

cout « “InOrder Traversal after inserting all nodes: " « endl; inorder(root); root = insert(root, -10); cout « “\nInOrder Traversal after inserting -10 : " « endl; inorder(root); cout « “\nSearching -5 in the BST: " « searchInBST(root, -5) « endl; cout « “Searching -10 in the BST: " « searchInBST(root, -10) « endl; root = deleteNode(root,8); cout«“After deleting node 8, inorder traversal: “«endl; inorder(root); root = deleteNode(root,-10); cout«"\nAfter deleting node -10, inorder traversal: “«endl; inorder(root); }

Output:

InOrder Traversal after inserting all nodes: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

InOrder Traversal after inserting -10 : 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Searching -5 in the BST: 0 Searching -10 in the BST: 1

After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15

After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15

Implementation of Binary Tree in Python

class Node: def init(self,value): self.left = None self.right = None self.value = value def insert(root,value): if root == None: return Node(value) if value< root.value: root.left = insert(root.left,value) else: root.right = insert(root.right,value) return root def searchInBST(root,value): current = root while current.value != value: if current.value > value: current = current.left else: current = current.right if current == None: return “Not found” return “Found” def inorder(root): if root != None: inorder(root.left) print(root.value,end=” “) inorder(root.right) def successor(root): present = root while present != None and present.left != None: present = present.left return present def deleteNode(root,value): if root == None: return root if value < root.value: root.left = deleteNode(root.left, value) elif value>root.value: root.right = deleteNode(root.right, value) else: if root.left == None: temp = root.right root = None return temp elif root.right == None: temp = root.left root = None return temp temp = successor(root.right) root.value = temp.value root.right = deleteNode(root.right, temp.value) return root root = Node(8) root = insert(root, 4) root = insert(root, 12) root = insert(root, 2) root = insert(root, 6) root = insert(root, 10) root = insert(root, 14) root = insert(root, 1) root = insert(root, 3) root = insert(root, 5) root = insert(root, 7) root = insert(root, 9) root = insert(root, 11) root = insert(root, 13) root = insert(root, 15) print(“InOrder Traversal after inserting all nodes: “) inorder(root) root = insert(root, -10) print("\nInOrder Traversal after inserting -10 : “) inorder(root) print("\nSearching -5 in the BST: “,searchInBST(root, -5)) print(“Searching -5 in the BST: “,searchInBST(root, -10)) root = deleteNode(root,8) print(“After deleting node 8, inorder traversal:”) inorder(root) root = deleteNode(root,-10) print("\nAfter deleting node -10, inorder traversal:”) inorder(root)

Output:

InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Searching -5 in the BST: Not found

Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15

After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15

Application of Binary Tree:

Here are some common applications of Binary Tree:

Organizing node data in sorted order Used in the map and set node objects in programming language libraries. Searching for elements in the data structures

» Learn our next tutorial about Combination Algorithm