# Introduction

Figure 1 shows a Binary Search Tree. This post will start with the motivation of studying BST and gradually move to the related definitions. We will do some hands on coding for simple BST operations and we will end the post by analysing the drawbacks.

# Where do we use Binary Search Tree?

• Trees show relationships in the data
• Trees have efficient insertion and searching
• Trees are flexible. It allows moving subtrees with minimum effort
• Binary Search Tree or BST is a data structure which can be used to store the data in a sorted manner
• BST can act as a priority queue, i.e. can help in retrieving maximum and minimum fast

# Terminology

We will discuss some terminology related to Binary Search Tree here:

## Node

A binary tree is made of nodes. Each node contains a reference to “left” and “right” element. It also has a data element . Root is the top most node of a tree. Figure 2 : Pictorial representation of a node. Referred here is the top most node with data element 4 as shown in figure 1

For any node A, except for the root node, we define parent node B as the node which connects A with a direct edge. Figure 3: Node A is the parent of node B and C. A is the root too

Each node can be connected to arbitrary number of nodes, also called as children. Nodes without children are called leaves or external nodes. Nodes other than external nodes are called internal nodes.

## Binary Tree

Any tree where all the nodes have at max two children is called Binary Tree. Figure 1 shows an example of Binary Tree.

## Binary Search Tree

Binary Search Tree is a special case of Binary Tree where all the data element of nodes to the left of any parent node is less than the data element of the parent node. Also, the data element of nodes to the right of any parent node is greater than the data element of the parent node.

Figure 1 is an example of a BST.

## Depth of a Node

Depth of a node is defined as number of edges from the root to the node. Node with data element 2 in figure 1 has depth of 1.

## Height of Node

The height of a node is defined as the number of edges from the node to the deepest leaf. Node with data element 2 in figure 1 has height of 1. Height of tree is the height of the parent node.

## Complete Binary Tree

A complete binary tree is a binary tree is defined as the tree in which each node has exactly zero or two children. Only possible exception can be bottom level, which is filled from left to right.

Figure 1 is an example of complete binary tree.

`Quick test. Is the test shown in figure 4 a complete binary tree?`

# Codes For Insertion, Search and Transversal

Searching in a BST has O(tree height) worst-case runtime complexity. Binary search tree with n nodes has a minimum of O(log n) levels. It will take at least O(log n) comparisons to find a particular node. A binary search tree can be hugely unbalanced, making the search time to O(n).

Node class.

# Disadvantage of Binary Search Tree

• The shape of the tree depends on the order of insertions. At worst case, tree can be hugely unbalanced. That means, we might have to travel all the way down the height of tree to find a key Figure 5: Searching 5 in the given tree will mean transversing the whole tree height
• Key of each visited node has to be compared with the key of the element to be inserted/found while inserting or searching. If key are long then the run time may increase.

Reference:

Introduction to Algorithm