Home

Learning Hub

Articles

Introduction to Binary Search Trees: Definition and Overview

Organizations can use different data structures to organize and store data in multiple forms. Data structures include different values, multiple functions, and their relationships to apply to data and function with certain algorithms. A binary search tree is a form of data structure, and you can learn all about it from this article. 

What is a Binary Search Tree?

A binary search tree includes nodes arranged in a predetermined sequence. The value of the root in a binary search tree is higher than the value of the nodes in the left sub-tree. Meanwhile, the root’s value usually equals or exceeds all the nodes in the right subtree. 

A binary search tree in data structures can be expressed as:

left_subtree (keys) < node (key) ≤ right_subtree (keys)

The Anatomy of Binary Search Trees

The different components of a binary search tree in the data structure are as follows:

• Nodes: Node refers to a termination point in any binary search tree in data structures. 
• Roots: The node on top of a binary tree is called the root. 
• Leaf Node: The external nodes with no child are called the leaf nodes. 
• Internal Node: All inner nodes with at least one child node are called internal nodes. 
• Parent: Apart from the root, all other nodes of the binary tree with a minimum of one subnode are a parent. 
• Child: The node rising straight from the parent node is the child.  
• Edge: An edge can indicate a relationship between two nodes by connecting them. 
• Depth/ Height of a Tree: The root or tree height signifies the highest number of edges from the farthest lead node to the edges. 

How Binary Search Trees Work?

The binary search tree data structure can support different basic operations like:

• Search
• Insert
• Find minimum
• Find maximum
• Delete
• Find the kth smallest element
• Find successor
• Find predecessor

The operations come with a time complexity of O(h), where h signifies the tree’s height. 

A balanced binary search tree includes the same number of nodes on the right and left subtrees of the root. In a balanced binary tree in a data structure, the above operations require O(log n) time (n= number of nodes in the tree). Meanwhile, the time required for operations in a linear binary search tree will be O(n).

On average, a randomly built binary search tree in the data structure has a height of O(log n). Therefore, the basic operations on a randomly built binary tree in data structure will need O(log n) time approximately. 

Explore: Linked List in Data Structure

Insertion in Binary Search Tree

You can insert a new element in a binary search tree only at the leaf. We should begin searching from the root node to add an element to a binary search tree. When the inserting node has a lesser value than the root, we will look for an empty location in the left subtree. 

But when the value of the data element is higher than the node, we will look for an empty space in the right subtree to insert a new element. Maintaining the property of the binary tree during insertion is crucial.

Deletion in Binary Search Tree

While performing deletion in a binary search tree, we can’t violate its fundamental property. Binary search trees can be deleted under the following circumstances:

• The leaf node is the target: We can replace the leaf node with NULL to empty the designated space.
• The target node comes with a single child: We can replace the target node with the child and later delete the child node.
• The target node comes with two children: We will have to find the successor of the node we wish to delete. Next, we can replace the target node with the successor as long as the target node is on the leaf. In the end, we should replace the target node with NULL to empty the allocated space. 

Searching in Binary Search Tree

A binary tree in data structures can help you search for a specific node or element. The steps to perform a search in a binary tree are as follows:

• Compare the element to be searched with the tree’s root value.
• If the root’s value is the same as the target element, return the node’s location.
• If the root’s value does not match the target element, check if the target is smaller or greater than the root element. Move to the right subtree if the root element is smaller, and move to the right subtree if the root element is greater.
• Continue with the procedure until you find a match.
• Return NULL if you can’t find the target element in the tree. 

Let’s look at some of the major advantages of the binary Search tree

• A binary tree in the data structure supports efficient searching by providing hints at every step regarding which subtree contains the target element.
• Compared to linked lists and arrays, a binary search tree is a more effective form of data structure. Each stage of the search procedure destroys half of the subtree. Moreover, a binary tree in the data structure ensures that you need O(log2n) time to search for an element. In the worst-case scenario, searching for an element will need no time at all. 
• Compared to arrays and linked lists, a binary tree in the data structure can perform insertion and deletion much faster. 

Read: Arrays in Data Structure: A Guide with Examples

Implementation of Binary Search Tree

The binary search tree in data structures gets implemented in the following steps:

Step 1: Read the user’s search element.

Step 2: Look for the middle element in the sorted list.

Step 3: Use the middle element in the sorted list to compare the search element.

Step 4: When both get matched, it shows “Given element is found!!!” The function also gets terminated. 

Step 5: When the elements don’t match, it’s necessary to determine whether the search element is larger or smaller than the middle element.

Step 6: When the search element is smaller than the middle element, it becomes necessary to execute steps 2,3,4 and 5 for the middle element’s left sublist.

Step 7: When the search element is larger than the middle element, it becomes necessary to repeat steps 2, 3, 4, and 5 for the middle element’s right sublist.

Step 8: If that element also fails to match the search element, it shows “Element is not found in the list!!!” After that, the function gets terminated. 

Read: What is Arrays in Java | Everything You Need to Know

What are the Real-World Applications of Binary Search Trees?

The different real-world applications of a binary search tree are as follows:

Routing Table

A routing table is useful for linking routers to a network. The trie data structure, a variation of the binary tree, is applicable for implementing routing tables. 

Decision Trees

Binary trees are often used for the purpose of classification. A decision tree is a form of a supervised machine-learning algorithm. The binary tree in a data structure is applied in decision tries for smooth decision-making.

Expression Evaluation

In mathematics, statements evaluating a value with operators and operands are called expressions. The binary tree leaves are the operands, while the internal nodes serve as the operators. 

Sorting

Binary search trees are useful for implementing sorting algorithms that can help order items. The items that need to be sorted are inserted in a binary search tree to begin the sorting procedure. The tree is traversed with the in-order traversal to retrieve the sorted items. 

Check out: Queue in Data Structure

What are the Types of Binary Search Trees

The different types of binary search trees are as follows:

• Balanced binary tree: In a balanced binary search tree, the height of the right and left subtrees of a node don’t differ by more than 1.
• Full binary tree: Each node in a full binary tree has two or zero children. 
• Complete binary tree: In a complete binary search tree, all tree levels, except for the lowest one, are occupied by nodes. 
• Perfect binary tree: The internal nodes of a perfect binary tree have a maximum of two children. Moreover, every lead node remains at the same level within the tree.
• Degenerate binary tree: In a degenerate or pathological binary tree, every node has a single child. 

Example of Binary Search Tree in Diagram

(Kindly replace this diagram with a new one)

Conclusion

A binary tree in data structures is immensely popular for searching. A binary search tree can be used for indexing, maintaining sorted data streams, and more. Additionally, a binary search tree in data structures is also implemented in different search algorithms.