Binary Search Tree
What is a Binary Search Tree?
BST(Binary Search Tree) is a non-linear data structure. It is a very efficient as it takes less time complexity than linked list or array for searching a node.
In Binary Search Tree the left sub tree elements are always smaller than the root node and the right sub tree elements are always greater than the root node. This makes searching and accessing of a node very easy as the other side sub tree is ignored.
Binary Search Tree Basics
Generally in binary search tree there will not be equal elements.
Binary Tree is a ordered and sorted data structure.
There are three types of traversal possible in binary search tree which are:
- Preorder
- In-order
- Postorder
In the above tree we have
Preorder
- Start with root node 21 and and recursively traverse the left subtree.
- Next node is 14 and traverse to left subtree of 14.
- Next node is 11 and traverse to left subtree of 11.
- Next node is 5 and 5 have no child so traverse to right subtree of 11
- Next node is 12 which have no child so traverse to right subtree of 14.
- 18 is the node now traverse to left subtree of 18.
- Next node is 15 which have no child so traverse to right subtree of 18.
- 19 is the new node.
- Now traverse to right side of the root node.
- 28 is the node and traverse to the left subtree of 28.
- Next node is 25 and traverse to the left subtree of 25.
- Next node is 23 and have no child so traverse to right subtree of 23.
- Next node is 26 which have no child so traverse to right subtree of 28.
- Next node is 32 and traverse to left subtree of 32.
- Next node is 31 and have no child so traverse to right subtree of 32.
- Next node is 33.
Pre order: 21 14 11 5 12 18 15 19 28 25 23 26 32 31 33