Home Data Structures Binary Search Tree Tutorial and Implementation

# Binary Search Tree Tutorial and Implementation

Binary Search Tree(BST) is a type of tree data structure which has the following properties:

1. It should be a Binary Tree i.e, each node should have at most 2 children.
2. The keys in the left subtree are always less than or equal to the root(parent) node
3. The keys in the right subtree are always greater than the root(parent) node.
4. The left and right subtree should also be a binary tree.

Example of BST:

This is a BST, as all nodes less than root node 8 are on the left, and all nodes greater than the root node 8 are on the left.

Also, all the subtrees also follow the BST property.

The height of this tree is 3.

##### Time Complexity for Various operation in BST
###### Worst Case
Height O(log N) O(N)
Search O(log N) O(N)
Insert O(log N) O(N)
Delete O(log N) O(N)
Tree Traversal O(N) O(N)

##### Tree Traversal

We have 3 algorithms for Tree Traversal:

1. Preorder -> (Root, Left, Right)
2. Inorder -> (Left, Root, Right)
3. Postorder -> (Left, Right, Root)

The time complexity of Tree traversal is O(N), where N is the number of nodes in the tree, because no matter which traversal method we use, we have to go and visit each element of a tree at least once, hence if there are N nodes then work done = asymptotic time to visit each node = O(N)

##### Best and Worst Case Height of BST

The BST has best-case height O(log N) when it is perfectly balanced, i.e, the height of the left subtree and right subtree is equal.

The BST has worst-case height O(N) if the tree is left or right-skewed.