A binary search tree (BST )is a type of binary tree in which the nodes are organise in a predetermined sequence. Additionally, This is referring as an ordered binary tree. The value of all nodes in the left sub-tree is less than the value of the root in a binary search tree.
Similarly, the value of all nodes in the right subtree is larger than or equal to the root’s value. This rule will applied recursively to all of the root’s left and right subtrees. As a result, BST separates all of its sub-trees into two segments: the left and right subtrees, and can be characterise as
left_subtree (keys) < node (key) ≤ right_subtree (keys)
Advantages
- In a BST, searching becomes incredibly efficient since we get a hint at each step about which sub-tree has the sought element.
- In comparison to arrays and linked lists, the binary search tree is a more efficient data structure. Every stage of the search procedure destroys half of the sub-tree. Furthermore, In a binary search tree, searching for an element takes o(log2n) time. In the worst-case scenario, searching for an element takes no time at all (n).
- It also speeds up insertion and deletion processes as compared to arrays and linked lists.
Operations
- Search – Looks for a specific element in a tree.
- Insert – Adds a new element to a tree.
- Pre – order traversal – Pre-orders the traversal of a tree.
- Post – order traversal – Traverses a tree in a logical order.
- In – order traversal – In a post-order fashion, traverses a tree.
Interested in learning about similar topics? Here are a few hand-picked blogs for you!
- What is data structure?
- Phenomena of sorting algorithm?
- What is API?
- Write about cloud computing?
- What is DNS?