How actually a Binary Search Tree works
Hello everyone, this is Aditya. N, i am here to share with you regarding what is a valid BST.
Prerequisites
Link: https://medium.com/@nagamalliaditya3/what-are-data-structures-846c3cacaff5
Dive Into Topic
- Assume that you have a array of numbers and need to find whether the Binary tree is a valid Binary Search Tree or not.
- Binary Search Tree means: In the name itself we are knowing it is fast access for Search the value from the tree.
- What are the rules need to be satisfied to become a valid Binary Search Tree.
How Binary Search Trees Work
Let’s Take an example and find out whether the Binary tree is a valid Binary Search Tree or not.
Example 1
- The Top Node is a Root / Parent Node ie 10 in the given set, The left Child Node is 8 and the right Child node is 15.
Step 2: Check first the root node had child or not. If child nodes are there noted down and find out whether they followed the Rules or not.
Step 3: The left child node is less than Root node and the Right Child node is greater than the root node. Condition satisfied. Now, check it had any Sub child's are there or not. If it had repeat the process.
step 4:No the given example is not a valid binary search tree. Because, for every immediate root node the right child node must be greater than the immediate root node. In this case, 6 omits the condition means fails. 6 is less than 8. So, its not a Valid Binary Search Tree.
Example 2:
Both, left and right sub trees must also be binary search trees.
Example 3:
Let’s consider this example and find out is this a valid BST ?
- In the given example Left Child Node and Right Child Node with Sub Nodes satisfies the basic principle. Here , we need to Observe the 1 is Less than Root Node 5 and 6 is Greater than 5,
6 had two childs 4 and 7 , 4 is less than 6 and 7 is greater than 6. Every condition we mentioned is satisfied but is it a valid BST ?
How Valid Binary Search Tree Looks Like
Here is an example ![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/9311to00hpii3ida7gz7.png)Conclusion
- We understood, how a valid binary search tree looks and how to evaluate without confusion or unnecessary ambiguity. I am always passionate to learn new things and share to everyone. If any mistakes are there feel free to comment.
- Sorry for the images i made it through online avaliable resources. If you know any animated or good resources to make gifs and good online resources comment below.
Top comments (0)