A binary search tree is one of the variants of the binary tree, also known as an ordered binary tree, in which the nodes are arranged in order by some rule mentioned below.
Node of binary search tree follows order mentioned below
- The value of all nodes in the left sub-tree or left child should be lesser than its root node value.
- The value of all nodes in the right sub-tree or right child should be greater than or equal to its root value.
- Each node should follow the above two rules at every height of the Binary search tree i.e., we can say that this rule will be recursively applied to all the left and right sub-trees of the root.
Binary search tree maintains
left_subtree (keys) < node (key) < right_subtree (keys)
- A binary search tree can be empty.
- The node of the binary search tree may contain both numerical as well as a string value.
- Binary Search Tree Numerical Order.
- Binary Search Tree Lexicographical Order.
Binary search tree operations
Search
Searches an element in a tree.
Insert
Inserts an element in a tree.
Pre-order Traversal
Traverse a tree in a pre-order manner means first to traverse the Root node, then the Left node, and at last Right node.
Traverse format : (Root, Left, Right)
In-order Traversal
Traverse a tree in an in-order manner means first to traverse the Left node, then the root node, and then at last Right node.
Traverse format : (Left, Root, Right)
Post-order Traversal
Traverse a tree in a post-order manner means the first traverse left node, then the right node, and the last root node.
Traverse format : (Left, Right, Root)
Advantages of using a binary search tree
- In BST, we get a hint at each step about elements while we perform a searching operation for an element.
- In the best case for searching an element, it takes o(log2n) time, and in the worst case, it takes 0(n) to search an element. This complexity is much better than the array and linked list for the same operation.
[wpusb]