What is Binary Search Tree? Everything you need to know

Different data structures help organize and store data in various forms in computer science. Data structures comprise a collection of data values, their relationships, and multiple functions that we can apply to data and work with using specific algorithms. There are various types of data structures, and the tree is one of them. Trees are non-linear data structures with a central node, structural nodes, and sub-nodes connected via edges. 

This article explores the concept of binary tree in data structure and binary search trees in detail.

What is the binary tree in data structure?

A binary tree is a non-linear data structure comprising nodes, and each parent has a maximum of two children. Each node in the tree contains the data element, the pointer to the left child, and a pointer to the right child. The node at the top of the hierarchy is the root node, and the nodes that carry the subnodes are called the parent nodes. Each parent node has two child nodes: the right child and the left child. 

Get Machine Learning Certification from the World’s top Universities. Earn Masters, Executive PGP, or Advanced Certificate Programs to fast-track your career.

The diagram below represents a binary tree data structure. 

Source

Terminologies Associated With Binary Trees

Now, let’s understand each terminology associated with binary tree data structures in more detail.

What is a binary search tree?

A binary search tree is a particular type of binary tree with three basic properties:

• The left subtree of a node has elements with values lower than the value of the node
• The right subtree of a node has elements with values greater than the value of the node
• Both the right and left subtrees should be binary search trees 

A binary search tree is named so because it increases the efficiency of search operation in a logarithmic tree. 

The illustration below explains what a binary search tree is (left) and what it is not (right).

Source

The binary tree on the right is not a binary search tree because the right subtree of the node “3” has a value (2) smaller than the node.

Binary Search Tree Example

Let’s understand the concept of binary search trees with an example:

Source

In the above figure, the root node is 25, and all the nodes of the left subtree are smaller than the root node. On the contrary, all the nodes of the right subtree are greater than the root node’s value.

Likewise, we can see that the right child of the root node (36) is greater than its left child (20), satisfying the condition of a binary search tree. The nodes “5,” “12,” “28,” “38,” and “48” are leaf nodes with no child. Thus, we can say that the binary tree in the above illustration is a binary search tree.

Types of Binary Trees

Binary trees have different kinds, and each has unique characteristics. The list below gives an overview of the different types of binary trees:

• Full binary tree: A full binary tree has either two or zero children. In other words, all the nodes in a full binary tree either have two children nodes, or the parent node itself is the external node or lead node. Thus, every node other than the external node has two children.

Source

• Perfect binary tree: In a perfect binary tree, all the internal nodes have a maximum of two children, and every leaf node is at the same depth or level within the tree. 

Source

• Complete binary tree: In a complete binary tree, nodes occupy all the tree levels except the tree’s lowest level. In addition, every node typically occupies the left side in the lowest level of the binary tree.

Source

• Degenerate binary tree: If every internal node in a binary tree has only a single child, it is known as a degenerate binary tree or a pathological binary tree. 

Source

• Balanced binary tree: A balanced binary tree or a height-balanced binary tree is one where the height of the left and the right subtrees of any node differ by not more than 1.

Source

Basic Operations in Binary Search Tree

Now, let’s briefly walk you through some of the basic operations you can perform on a binary search tree:

1. Search

Searching in a binary search tree means finding a specific node or element in a data structure. Below are the steps to search a node in a binary search tree:

• Compare the element to be searched with the root value of the tree.
• Return the node’s location if the root’s value matches the target element.
• If the root’s value does not match the target element, check if the latter is smaller than the root element. If yes, then move to the left subtree.
• If the target element is larger than the root, move to the right subtree.
• Repeat the above procedure until the match is found.
• Return NULL if the target element is not found in the tree.

Consider the following binary search tree and suppose we have to search for the node “20.”

Source

Steps illustrating how to find the node “20” in the binary search tree:

Source

2. Insert

Inserting a new element in a binary search tree always takes place at the leaf. We start searching from the root node to insert an element in a binary search tree. If the inserting node has a value less than the root, we search for an empty location in the left subtree. On the contrary, if our data element’s value is greater than the node, we search for an empty place in the right subtree and insert the element. We must maintain the binary search tree property during insertion that the right subtree is larger than the root and the left subtree is smaller than the root.

The following diagram illustrates the insertion process in a binary search tree:

Source

3. Delete

We must keep in mind not to violate the fundamental property of a binary search tree while performing the deletion operation. Binary search tree nodes can be deleted using three possible situations:

• The target node is the leaf node: We replace the leaf node with NULL and free the allocated space.

Source

• The target node has only one child: In this case, we replace the target node with its child, followed by deleting the child node.

Source

• The target node has two children: In this case, we first find the inorder successor of the node we want to delete. Then, we replace the target node with the inorder successor until the target node is at the tree’s leaf. Finally, replace the target node with NULL and free up the designated space.

 Source

Wrapping Up

A binary search tree is a popular searching technique with applications in indexing, multi-level indexing, and maintenance of a sorted stream of data. Binary search trees are also widely used to implement various searching algorithms.

Search algorithms also form a fundamental component of artificial intelligence and machine learning problems. If you are interested to learn more, check out upGrad’s Master of Science in Machine Learning & AI in collaboration with Liverpool John Moores University. 

The 20-month online program is best suited for candidates who wish to learn in-demand skills such as deep learning, NLP, and reinforcement learning with hands-on experience in 12+ industry projects, multiple programming languages and tools, and a master dissertation.

Sign up today to get exclusive upGrad advantages, including 360-degree career assistance, peer-to-peer learning, and networking.