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:
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 –
