What is a Valid Binary Search Tree
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
- Familiar with Basic idea of Data Structures
- What actually trees are how it is different from Binary Tree
I hope you are familiar with Data Structures and Trees Concept. If not don’t worry take a look at this article you got an idea what are they.
Link
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
- Every parent/ root node has at most two children.
- Every node to the left of a parent/ root node is always less than the parent / root node.
- Every node to the right of a parent node is always greater than the parent / root node.
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 ?
It is Invalid Because, remember every child node in the right side of parent node should be greater than parent node.
4 is less than Root Node 5 that’s why it is a invalid Binary Search Tree.
How Valid Binary Search Tree Looks Like
Here is an example
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.
