What is Binary Search Tree? Everything you need to know
Updated on Feb 04, 2025 | 10 min read | 6.1k views
Share:
For working professionals
For fresh graduates
More
Updated on Feb 04, 2025 | 10 min read | 6.1k views
Share:
Table of Contents
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.
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.
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.
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. |
A binary search tree is a particular type of binary tree with three basic properties:
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).
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.
Let’s understand the concept of binary search trees with an example:
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.
Binary trees have different kinds, and each has unique characteristics. The list below gives an overview of the different types of binary trees:
Now, let’s briefly walk you through some of the basic operations you can perform on a binary search tree:
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:
Consider the following binary search tree and suppose we have to search for the node “20.”
Steps illustrating how to find the node “20” in the binary search tree:
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:
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:
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.
Get Free Consultation
By submitting, I accept the T&C and
Privacy Policy
Top Resources