What is Binary Search Tree? Everything you need to know

# What is Binary Search Tree? Everything you need to know

Last updated:
17th Sep, 2022
Views
10 Mins
View All

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.

## Our AI & ML Programs in US

 Master of Science in Machine Learning & AI from LJMU and IIITB Executive PG Program in Machine Learning & Artificial Intelligence from IIITB To Explore all our courses, visit our page below. Machine Learning Courses

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.

 Terminology Description 1. Node A node represents a termination point in a binary tree. 2. Root A root is a binary tree’s topmost node. 3. Parent Any node of the binary tree (besides the root) with at least one subnode of its own is a parent. 4. Child As you move away from the root, the node that arises straight from the parent node is the child. 5. Internal node These are inner nodes with a minimum of one child node. 6. Leaf node These are the external nodes with no child. 7. Edge An edge connects two nodes to indicate a relationship between them. 8. Height/depth of a tree The tree height or the root height represents the largest number of edges from the root to the farthest leaf node.

## 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.

• 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.

• 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.

• 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.

• 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.

## Popular AI and ML Blogs & Free Courses

 IoT: History, Present & Future Machine Learning Tutorial: Learn ML What is Algorithm? Simple & Easy Robotics Engineer Salary in India : All Roles A Day in the Life of a Machine Learning Engineer: What do they do? What is IoT (Internet of Things) Permutation vs Combination: Difference between Permutation and Combination Top 7 Trends in Artificial Intelligence & Machine Learning Machine Learning with R: Everything You Need to Know AI & ML Free Courses Introduction to NLP Fundamentals of Deep Learning of Neural Networks Linear Regression: Step by Step Guide Artificial Intelligence in the Real World Introduction to Tableau Case Study using Python, SQL and Tableau

## 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.

#### Rohan Vats

Blog Author
Software Engineering Manager @ upGrad. Passionate about building large scale web apps with delightful experiences. In pursuit of transforming engineers into leaders.
Get Free Consultation

Select Course
Select
By clicking 'Submit' you Agree to

#### Our Best Artificial Intelligence Course

1What are binary trees and their types?

A binary tree is a non-linear data structure with at most two children for each parent node. The node at the top of the tree is the root node, and the nodes that carry other sub-nodes are called parent nodes. Binary trees can be of five types: full, complete, perfect, balanced, and degenerate.

2Can a binary tree have one child?

A degenerate binary tree is where every internal node has a single child.

3What is a perfect binary tree?

A perfect binary tree is one type of binary tree where every internal node has a maximum of two child nodes, and all the leaf nodes are at the same tree level.

## Suggested Blogs

5446
A CNN (Convolutional Neural Network) is a type of deep learning neural network that uses a combination of convolutional and subsampling layers to lear

15 Apr 2023

5249
What is a Speech Recognition Software? Speech Recognition Software programs are computer programs that interpret human speech and convert it into tex

by Sriram

26 Feb 2023

5255
Artificial intelligence controls computers to resemble the decision-making and problem-solving competencies of a human brain. It works on tasks usuall

by Sriram

26 Feb 2023

5158
Taking on machine learning projects as a beginner is an excellent way to gain hands-on experience and develop a better understanding of the fundamenta

by Sriram

26 Feb 2023

5137
A CNN (Convolutional Neural Network) is a type of deep learning neural network that uses a combination of convolutional and subsampling layers to lear

by Sriram

26 Feb 2023

5792
IoT (Internet of Things) is a network that houses multiple smart devices connected to one Cloud source. This network can be regulated in several ways

by Sriram

25 Feb 2023

5785
Time complexity is a measure of the amount of time needed to execute an algorithm. It is a function of the algorithm’s input size and the type o

by Sriram

25 Feb 2023

7174
Machine learning can effectively analyze data with several dimensions. However, it becomes complex to develop relevant models as the number of dimensi

by Sriram

25 Feb 2023

5618
Artificial Intelligence is a field of science that enables computers and machines to perform various functions, including the ability to learn, reason