Binary Search Tree
Welcome !! In this article, we will be learning about Binary Search Trees.
The main thing to understand about tree data structure is that each node has an associated value with it. As we all know, each node contains left and right nodes. A Binary Search Tree is a Binary tree in which each node’s left child is smaller than the node’s value, and each right child is larger.
If there is at least one single node that does not satisfy the above condition then the tree is not a Binary search tree. In the below example we can see that a node with key 1 is lesser than 6 but it is present at the right subtree of node 6, and node 4 is smaller than 5 but it is in the right subtree of 5. Hence, the below tree is not considered as a Binary Search Tree.
Key Takeaways:
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
How to search for values in BST
As the name suggests, the most common use of BST is to search for a value. Since the BST follows a condition while storing the data, it is easy to search for a node. Start from root, if the node you are searching is less than root, go left, otherwise, go right. simple! Let's say you are looking for node 6.
How to insert values into BST
Inserting a value into BST is similar to searching. If the node you want to insert is lesser than the root, take left. If it's more, go right. One condition is that you should not insert a value that already exists. So while traversing through the tree, check whether the current node is equal or not with the node that you want to insert. If it does, just throw an error or do nothing at all.
Conclusion
Binary search trees are a very powerful data structure to have in your programming tool belt. If done right, handling large amounts of sorted data becomes easier and quicker.
