Binary Search Tree Introduction & Properties
Binary Search Trees
- It is type of binary tree.
- Value of all nodes of the left subtree are lesser than the node itself (root node).
- Value of all nodes of the right subtree are greater than the node itself.
- Left and RIght subtrees are also binary search trees.
- There are no duplicate nodes.
Is this a binary seach tree?
The answer is no. Since the left subtree of the root node has a single element that is greater
then the root node vialating the 2nd property, hence it is not a binary search tree.
Is this a binary seach tree?
The answer is no because the left subtree is good but the right subtree of the root node is
lesser than the root node itself violating the 3rd property.
Analize this one
For a binary tree this big, it will take time. So the faster way is using a property.
InOrder traversal of a binary search tree gives an ascending sorted array.
For InOrder traversal we use easy method that is
- we put line below each node and start making line from the root node, if the line touches any node we write it
- for PostOrder the line is at the left side
- for preOrder the line is at the right side
↓
So, the final InOrder traversal order of the above tree is
2 → 4 → 5 → 6 → 7 → 8 → 9 → 11 → 14 → 15
Which is obviously in increasingly sorted order. Hence, it is a binary search tree.