We utilize binary search trees because...

The use of a binary search tree is beneficial in any situation where the elements may be compared in a less than/greater than method. To evaluate if one piece is more or less important than another in our example, we'll use alphabetical order (for instance, "Alan" vs. "Bob" vs. "Dave" vs. "John" vs. "Kyle" vs. "Leonard" vs. "zack").

start from the source. If the search key is smaller than the index key of the element, go to the left child. If the search key is greater than the element's index key, go to the appropriate child.

Once the element is located, the index key and search key match, and the tree's end is reached (in which case the element is not present. After three comparisons, we can definitively state that either the element does not exist or that it has been discovered. We will save more time by using a binary search tree when the array is larger. We will need to perform 7 comparisons on the array to extract the same data.

Searching is faster than other methods without a doubt, but what about those? A binary search tree often performs better than an array in terms of how few operations are needed to add or remove an entry. Place the data in the first memory address my Array[my Array. length] (which is more equivalent to pushing onto a stack) to add an element to the end of an array. It will If you want to add an element to the beginning of an array, you must relocate every element. The same is true for deletion. You only need to change the array's stored length if the element is at the end (like popping off a stack).

But if you take off the first piece, you have to alter all the others. The binary search tree does not require that its elements be kept in a continuous block of memory, allowing for the insertion and deletion of nodes by just changing a few pointers. A node is a struct that holds information and references to the variables on the left child and right child.

The nodes of a binary tree called a binary search tree each contain a key and a potential corresponding value. It facilitates swift object addition, removal, and lookup.

The nodes in a binary search tree are arranged according to the following properties:

The left subtree of a given node always contains nodes with keys lower than that node's key.

A node will always be located in the appropriate subtree if another node has a key larger than that node's key.

The left and right subtrees of a given node are both binary search trees.

You can carry out the following three essential operations on a binary search tree:

1. Search

The approach is based on the BST attribute that each left sub tree has values below the root and each right sub tree has values above the root.

We only need to look in the right sub tree if the value is above the root because we are assured it is not in the left sub tree. Similar to the previous example, if the value is below the root, we know it is not on the right sub tree and only need to look in the left sub tree.

2. Insert

Inserting a value in the appropriate location is similar to searching since we strive to enforce the restriction that the left sub tree is smaller than the root and the right sub tree is larger than the root.

We insert the new node where the left or right sub tree is null by continuously advancing to the right or left sub tree, depending on the value.

3. Remove

One of three scenarios allows for the deletion of a binary search tree.

Case I

The node that needs to be removed in the first instance is the leaf node. In this case, remove the node from the tree.

Case II

Do the following in this circumstance:

Place the node's descendent in its place.

It is necessary to reposition the child node from its initial location.

Case III

The deleted node in the third scenario has two progeny. Do the following in this circumstance:

Obtain those nodes in succeeding order.

Replace the node with the in-order successor.

It should be moved from where it was originally placed to the in-order successor.

Conclusion

Numerous real-world uses exist for binary search, including looking for a particular word in a dictionary or an element in a sizable database. The array must first be sorted before doing a binary search, it is vital to remember. A linear search may be more suitable if the array is not sorted.

The binary search tree is a part of the Data structure and algorithms course. The best DSA courses in Bangalore are provided by Tutort Academy they also have DSA Live Classes .