EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Binary Search Tree Properties
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Binary Search Tree Properties

Binary Search Tree Properties

Introduction to Binary Search Tree Properties

Binary search tree properties are defined as characteristics and traits that helps in describing a search tree to be a binary search tree. Binary search tree is defined as a sorted and ordered tree that belongs to the class of rooted tree, a tree where one vertex is chosen as the root through which other branches are assigned a natural orientation (either towards or away from the root), type of data structure.

This binary search tree allows developers to conduct fast lookups, insertion or removal of any root item and hence an obvious choice for any dynamic sets or lookup tables. The word binary here refers to the split that happens when another number either needs to be inserted, or a number that is to be searched is found after traversing the tree.

Various Binary Search Tree Properties

Now we know the tree characteristics of a binary search tree it is very important to know the properties so that when we, later on in this article, look into the basic operations at a superficial level we can easily connect on the importance of a binary tree that helps us to perform the operations in an easier way.

The following are the properties of a node-based binary tree:

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

1. The left subtree of the binary search tree contains those values that are lesser than the node’s key. While performing this, it is not necessary that the tree should have an equal number of left nodes and right nodes. Though the ask is not unrealistic, the tree that is asked for having an equal number of left and right nodes or at the max one extra node either on the left or right is known as a balanced binary search tree. With this characteristic, we can maintain that the numbers on the left side of the tree are lesser and hence needs to be traversed in case then we want to travel the path to perform an operation that focuses on the lesser numbers.

2. On the same lines, the next characteristic of the binary tree is that the right subtree contains values that are greater than the node’s key. Likewise, to the earlier point, while performing this, it is not necessary that the tree should have an equal number of right nodes and left nodes. With this characteristic, we can maintain that the numbers on the right side of the tree are greater and hence needs to be traversed in case then we want to travel the path to perform an operation that focusses on the greater numbers.

3. Last but not the least property is that each of the subtrees that is formed should be a binary tree as a standalone, which essentially means that when we cut the full tree at any node, the resulting tree should be a binary search tree in itself. This property is the most crucial one because it helps maintain the previous 2 points in the subtrees so that the path to be traversed is the shortest one.

Let us look at an example. Let us say we have to search for a number in the tree. Now assume that only at the root node, we apply the previous 2 points. Now if we traverse, we know that we need to traverse on the right or the left side depending on the value being greater or lesser than the root node.

Now, arises 2 conditions:

  • The sub trees are not individually binary search trees: In this scenario, it is very difficult to understand the path that needs to be traversed as we don’t know which side of the tree would contain the number that is to be searched for.
  • The sub trees are not individually binary search trees: In this scenario, it becomes very easy to understand the path that needs to be traversed as we would know which side of the tree should be traversed so that we find the appropriate path that would contain the number that is to be searched for.

With the above properties, it becomes even easier to keep the sanity of the binary search tree to be used for the use case that is built for. Let us look at the operations that a binary search tree exploits the properties we have mentioned and helps in the easiest traversal of the tree.

  • Search: The first operation that a binary tree has to look at is the search. Now, during this operation, we input the number that needs to be searched for. At first, we would compare it to the number at the root node. Now if the number over there is found then great. Otherwise, we would see if the number is lesser than or greater than the root node. Now depending on the scenario either the first or the second property is exploited, and that path is taken. Now since the third property says that the subtree should also be a binary search tree, hence the similar steps are followed till we reach a node that is either the number we are searching for or the leaf node (node post which we don’t have any other nodes).
  • Delete and Insert: In both these operations, we would need to use the search operation and hence the properties gets used in accordance to the need and when we reach that specific node, either the insert or the delete operation is performed as per the need of the use case.

Conclusion

We have looked into the properties of the binary search tree in great detail. This article also enabled us to link how properties are linked to operation in a binary search tree and also see the importance of properties which keeps the sanctity of the binary search tree on its use cases.

Recommended Articles

This is a guide to Binary Search Tree Properties. Here we discuss the introduction and various binary search tree properties respectively. You may also have a look at the following articles to learn more –

  1. Binary Search Tree Types
  2. Inorder Traversal of Binary Tree
  3. Binary Tree in Data Structure
  4. Tree Traversal Techniques
Popular Course in this category
Data Scientist Training (85 Courses, 67+ Projects)
  85 Online Courses |  67 Hands-on Projects |  660+ Hours |  Verifiable Certificate of Completion
4.8
Price

View Course

Related Courses

All in One Data Science Bundle (360+ Courses, 50+ projects)4.9
Oracle DBA Database Management System Training (2 Courses)4.8
SQL Training Program (7 Courses, 8+ Projects)4.7
0 Shares
Share
Tweet
Share
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2022 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

SPSS, Data visualization with Python, Matplotlib Library, Seaborn Package

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more