Explore Courses
Liverpool Business SchoolLiverpool Business SchoolMBA by Liverpool Business School
  • 18 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityMBA (Master of Business Administration)
  • 15 Months
Popular
O.P.Jindal Global UniversityO.P.Jindal Global UniversityMaster of Business Administration (MBA)
  • 12 Months
New
Birla Institute of Management Technology Birla Institute of Management Technology Post Graduate Diploma in Management (BIMTECH)
  • 24 Months
Liverpool John Moores UniversityLiverpool John Moores UniversityMS in Data Science
  • 18 Months
Popular
IIIT BangaloreIIIT BangalorePost Graduate Programme in Data Science & AI (Executive)
  • 12 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityDBA in Emerging Technologies with concentration in Generative AI
  • 3 Years
upGradupGradData Science Bootcamp with AI
  • 6 Months
New
University of MarylandIIIT BangalorePost Graduate Certificate in Data Science & AI (Executive)
  • 8-8.5 Months
upGradupGradData Science Bootcamp with AI
  • 6 months
Popular
upGrad KnowledgeHutupGrad KnowledgeHutData Engineer Bootcamp
  • Self-Paced
upGradupGradCertificate Course in Business Analytics & Consulting in association with PwC India
  • 06 Months
OP Jindal Global UniversityOP Jindal Global UniversityMaster of Design in User Experience Design
  • 12 Months
Popular
WoolfWoolfMaster of Science in Computer Science
  • 18 Months
New
Jindal Global UniversityJindal Global UniversityMaster of Design in User Experience
  • 12 Months
New
Rushford, GenevaRushford Business SchoolDBA Doctorate in Technology (Computer Science)
  • 36 Months
IIIT BangaloreIIIT BangaloreCloud Computing and DevOps Program (Executive)
  • 8 Months
New
upGrad KnowledgeHutupGrad KnowledgeHutAWS Solutions Architect Certification
  • 32 Hours
upGradupGradFull Stack Software Development Bootcamp
  • 6 Months
Popular
upGradupGradUI/UX Bootcamp
  • 3 Months
upGradupGradCloud Computing Bootcamp
  • 7.5 Months
Golden Gate University Golden Gate University Doctor of Business Administration in Digital Leadership
  • 36 Months
New
Jindal Global UniversityJindal Global UniversityMaster of Design in User Experience
  • 12 Months
New
Golden Gate University Golden Gate University Doctor of Business Administration (DBA)
  • 36 Months
Bestseller
Ecole Supérieure de Gestion et Commerce International ParisEcole Supérieure de Gestion et Commerce International ParisDoctorate of Business Administration (DBA)
  • 36 Months
Rushford, GenevaRushford Business SchoolDoctorate of Business Administration (DBA)
  • 36 Months
KnowledgeHut upGradKnowledgeHut upGradSAFe® 6.0 Certified ScrumMaster (SSM) Training
  • Self-Paced
KnowledgeHut upGradKnowledgeHut upGradPMP® certification
  • Self-Paced
IIM KozhikodeIIM KozhikodeProfessional Certification in HR Management and Analytics
  • 6 Months
Bestseller
Duke CEDuke CEPost Graduate Certificate in Product Management
  • 4-8 Months
Bestseller
upGrad KnowledgeHutupGrad KnowledgeHutLeading SAFe® 6.0 Certification
  • 16 Hours
Popular
upGrad KnowledgeHutupGrad KnowledgeHutCertified ScrumMaster®(CSM) Training
  • 16 Hours
Bestseller
PwCupGrad CampusCertification Program in Financial Modelling & Analysis in association with PwC India
  • 4 Months
upGrad KnowledgeHutupGrad KnowledgeHutSAFe® 6.0 POPM Certification
  • 16 Hours
O.P.Jindal Global UniversityO.P.Jindal Global UniversityMaster of Science in Artificial Intelligence and Data Science
  • 12 Months
Bestseller
Liverpool John Moores University Liverpool John Moores University MS in Machine Learning & AI
  • 18 Months
Popular
Golden Gate UniversityGolden Gate UniversityDBA in Emerging Technologies with concentration in Generative AI
  • 3 Years
IIIT BangaloreIIIT BangaloreExecutive Post Graduate Programme in Machine Learning & AI
  • 13 Months
Bestseller
IIITBIIITBExecutive Program in Generative AI for Leaders
  • 4 Months
upGradupGradAdvanced Certificate Program in GenerativeAI
  • 4 Months
New
IIIT BangaloreIIIT BangalorePost Graduate Certificate in Machine Learning & Deep Learning (Executive)
  • 8 Months
Bestseller
Jindal Global UniversityJindal Global UniversityMaster of Design in User Experience
  • 12 Months
New
Liverpool Business SchoolLiverpool Business SchoolMBA with Marketing Concentration
  • 18 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityMBA with Marketing Concentration
  • 15 Months
Popular
MICAMICAAdvanced Certificate in Digital Marketing and Communication
  • 6 Months
Bestseller
MICAMICAAdvanced Certificate in Brand Communication Management
  • 5 Months
Popular
upGradupGradDigital Marketing Accelerator Program
  • 05 Months
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Corporate & Financial Law
  • 12 Months
Bestseller
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in AI and Emerging Technologies (Blended Learning Program)
  • 12 Months
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Intellectual Property & Technology Law
  • 12 Months
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Dispute Resolution
  • 12 Months
upGradupGradContract Law Certificate Program
  • Self paced
New
ESGCI, ParisESGCI, ParisDoctorate of Business Administration (DBA) from ESGCI, Paris
  • 36 Months
Golden Gate University Golden Gate University Doctor of Business Administration From Golden Gate University, San Francisco
  • 36 Months
Rushford Business SchoolRushford Business SchoolDoctor of Business Administration from Rushford Business School, Switzerland)
  • 36 Months
Edgewood CollegeEdgewood CollegeDoctorate of Business Administration from Edgewood College
  • 24 Months
Golden Gate UniversityGolden Gate UniversityDBA in Emerging Technologies with Concentration in Generative AI
  • 36 Months
Golden Gate University Golden Gate University DBA in Digital Leadership from Golden Gate University, San Francisco
  • 36 Months
Liverpool Business SchoolLiverpool Business SchoolMBA by Liverpool Business School
  • 18 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityMBA (Master of Business Administration)
  • 15 Months
Popular
O.P.Jindal Global UniversityO.P.Jindal Global UniversityMaster of Business Administration (MBA)
  • 12 Months
New
Deakin Business School and Institute of Management Technology, GhaziabadDeakin Business School and IMT, GhaziabadMBA (Master of Business Administration)
  • 12 Months
Liverpool John Moores UniversityLiverpool John Moores UniversityMS in Data Science
  • 18 Months
Bestseller
O.P.Jindal Global UniversityO.P.Jindal Global UniversityMaster of Science in Artificial Intelligence and Data Science
  • 12 Months
Bestseller
IIIT BangaloreIIIT BangalorePost Graduate Programme in Data Science (Executive)
  • 12 Months
Bestseller
O.P.Jindal Global UniversityO.P.Jindal Global UniversityO.P.Jindal Global University
  • 12 Months
WoolfWoolfMaster of Science in Computer Science
  • 18 Months
New
Liverpool John Moores University Liverpool John Moores University MS in Machine Learning & AI
  • 18 Months
Popular
Golden Gate UniversityGolden Gate UniversityDBA in Emerging Technologies with concentration in Generative AI
  • 3 Years
Rushford, GenevaRushford Business SchoolDoctorate of Business Administration (AI/ML)
  • 36 Months
Ecole Supérieure de Gestion et Commerce International ParisEcole Supérieure de Gestion et Commerce International ParisDBA Specialisation in AI & ML
  • 36 Months
Golden Gate University Golden Gate University Doctor of Business Administration (DBA)
  • 36 Months
Bestseller
Ecole Supérieure de Gestion et Commerce International ParisEcole Supérieure de Gestion et Commerce International ParisDoctorate of Business Administration (DBA)
  • 36 Months
Rushford, GenevaRushford Business SchoolDoctorate of Business Administration (DBA)
  • 36 Months
Liverpool Business SchoolLiverpool Business SchoolMBA with Marketing Concentration
  • 18 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityMBA with Marketing Concentration
  • 15 Months
Popular
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Corporate & Financial Law
  • 12 Months
Bestseller
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Intellectual Property & Technology Law
  • 12 Months
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Dispute Resolution
  • 12 Months
IIITBIIITBExecutive Program in Generative AI for Leaders
  • 4 Months
New
IIIT BangaloreIIIT BangaloreExecutive Post Graduate Programme in Machine Learning & AI
  • 13 Months
Bestseller
upGradupGradData Science Bootcamp with AI
  • 6 Months
New
upGradupGradAdvanced Certificate Program in GenerativeAI
  • 4 Months
New
KnowledgeHut upGradKnowledgeHut upGradSAFe® 6.0 Certified ScrumMaster (SSM) Training
  • Self-Paced
upGrad KnowledgeHutupGrad KnowledgeHutCertified ScrumMaster®(CSM) Training
  • 16 Hours
upGrad KnowledgeHutupGrad KnowledgeHutLeading SAFe® 6.0 Certification
  • 16 Hours
KnowledgeHut upGradKnowledgeHut upGradPMP® certification
  • Self-Paced
upGrad KnowledgeHutupGrad KnowledgeHutAWS Solutions Architect Certification
  • 32 Hours
upGrad KnowledgeHutupGrad KnowledgeHutAzure Administrator Certification (AZ-104)
  • 24 Hours
KnowledgeHut upGradKnowledgeHut upGradAWS Cloud Practioner Essentials Certification
  • 1 Week
KnowledgeHut upGradKnowledgeHut upGradAzure Data Engineering Training (DP-203)
  • 1 Week
MICAMICAAdvanced Certificate in Digital Marketing and Communication
  • 6 Months
Bestseller
MICAMICAAdvanced Certificate in Brand Communication Management
  • 5 Months
Popular
IIM KozhikodeIIM KozhikodeProfessional Certification in HR Management and Analytics
  • 6 Months
Bestseller
Duke CEDuke CEPost Graduate Certificate in Product Management
  • 4-8 Months
Bestseller
Loyola Institute of Business Administration (LIBA)Loyola Institute of Business Administration (LIBA)Executive PG Programme in Human Resource Management
  • 11 Months
Popular
Goa Institute of ManagementGoa Institute of ManagementExecutive PG Program in Healthcare Management
  • 11 Months
IMT GhaziabadIMT GhaziabadAdvanced General Management Program
  • 11 Months
Golden Gate UniversityGolden Gate UniversityProfessional Certificate in Global Business Management
  • 6-8 Months
upGradupGradContract Law Certificate Program
  • Self paced
New
IU, GermanyIU, GermanyMaster of Business Administration (90 ECTS)
  • 18 Months
Bestseller
IU, GermanyIU, GermanyMaster in International Management (120 ECTS)
  • 24 Months
Popular
IU, GermanyIU, GermanyB.Sc. Computer Science (180 ECTS)
  • 36 Months
Clark UniversityClark UniversityMaster of Business Administration
  • 23 Months
New
Golden Gate UniversityGolden Gate UniversityMaster of Business Administration
  • 20 Months
Clark University, USClark University, USMS in Project Management
  • 20 Months
New
Edgewood CollegeEdgewood CollegeMaster of Business Administration
  • 23 Months
The American Business SchoolThe American Business SchoolMBA with specialization
  • 23 Months
New
Aivancity ParisAivancity ParisMSc Artificial Intelligence Engineering
  • 24 Months
Aivancity ParisAivancity ParisMSc Data Engineering
  • 24 Months
The American Business SchoolThe American Business SchoolMBA with specialization
  • 23 Months
New
Aivancity ParisAivancity ParisMSc Artificial Intelligence Engineering
  • 24 Months
Aivancity ParisAivancity ParisMSc Data Engineering
  • 24 Months
upGradupGradData Science Bootcamp with AI
  • 6 Months
Popular
upGrad KnowledgeHutupGrad KnowledgeHutData Engineer Bootcamp
  • Self-Paced
upGradupGradFull Stack Software Development Bootcamp
  • 6 Months
Bestseller
KnowledgeHut upGradKnowledgeHut upGradBackend Development Bootcamp
  • Self-Paced
upGradupGradUI/UX Bootcamp
  • 3 Months
upGradupGradCloud Computing Bootcamp
  • 7.5 Months
PwCupGrad CampusCertification Program in Financial Modelling & Analysis in association with PwC India
  • 5 Months
upGrad KnowledgeHutupGrad KnowledgeHutSAFe® 6.0 POPM Certification
  • 16 Hours
upGradupGradDigital Marketing Accelerator Program
  • 05 Months
upGradupGradAdvanced Certificate Program in GenerativeAI
  • 4 Months
New
upGradupGradData Science Bootcamp with AI
  • 6 Months
Popular
upGradupGradFull Stack Software Development Bootcamp
  • 6 Months
Bestseller
upGradupGradUI/UX Bootcamp
  • 3 Months
PwCupGrad CampusCertification Program in Financial Modelling & Analysis in association with PwC India
  • 4 Months
upGradupGradCertificate Course in Business Analytics & Consulting in association with PwC India
  • 06 Months
upGradupGradDigital Marketing Accelerator Program
  • 05 Months

What is Binary Search Tree? Everything you need to know

Updated on 30 November, 2022

5.87K+ views
10 min read
What is Binary Search Tree

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.

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.

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.

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. 

Frequently Asked Questions (FAQs)

1. What 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.

2. Can a binary tree have one child?

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

3. What 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.

Did you find this article helpful?

Rohan Vats

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

See More

Get Free Consultation

+91
Phone number

By clicking "Submit" you Agree toupGrad's Terms & Conditions