Binary Search Tree
date
Jan 29, 2024
slug
binary-search-tree
status
Published
tags
summary
type
Post
What is binary search tree?
A binary search tree (BST) is a hierarchical data structure for organizing and storing elements in a way that allows for efficient search, insertion, and deletion operations
It is called a "binary" search tree because each node in the tree has at most two children, referred to as the left child and the right child.
Feature of Binary Search Tree
- Each Node has two sub nodes left node and right node
- Left Node must be less than it’s immediate parent node.
- Right Node must be greater than it’s immedite parent node.
Example
Let’s see how elements [100, 2 , 105, 10, 1, 101] is saved as BST
As you can see, structure of Tree entirely depends on the order of insertioin.
Note: Structure of Tree affects the time complexity of insertion, deletion, and search operations.
If the order of strictly ascending or decending, structure of tree will be similar to linked list.
Example - 1 2 3 4
Example - 4 3 2 1
Add Operation
Add operation is pretty straightforward in binary search tree.
Because of the fact that:
- Each Node has two sub nodes left node and right node
- Left Node must be less than it’s immediate parent node.
- Right Node must be greater than it’s immedite parent node.
Search Operation
Search operation is pretty straightforward in binary search tree. It is similar to add operation.