Search Algorithms || Binary Search Tree || Part 1

What are Search Algorithms?

Search Algorithms provide us with fast search mechanism. Not only search, but insertion and deletion also becomes faster. These sort of Algorithms are normally explored under the subject Data Structures. There are different algorithms like binary search, binary search tree, minHeap, etc. 

In this post and some upcoming posts, I'll be explaining Binary Search Tree. So let's begin.

Binary Search Tree

In binary search tree, the data is divided into halves and there is a root element. There are nodes in the tree. 

• Each node has zero, one or two children. 
• Each node has only one parent. But may have grand parents, great grant parents and so on :P
• Nodes that have zero children are called leaves.
• Each tree has a height, which is number of jumps/edges from the root to the most distant leaf.
• Similarly, height of a node is the number of jumps/edges from the node to most distant leaf.

Height of the root is the height of the tree.

In the image given above, you can observe a binary tree. The height of this tree is 2. Root has two children, right and left children. The right child of the root has only one child i.e. a left child. While the left child of the root has two children which is the maximum number of children a node can have. The blue nodes are the leaves of these tree. 

A tree may not necessarily have all the leaves at the same level e.g.

in the image on the right. In this image, there are still 3 leaves i.e. 2 blue nodes and the right child of the root.

The data in a binary tree is sorted, for instance, let's take a binary tree that stores integers in the nodes. On the left of the root, there will be integers smaller than the root and on the right there will be integers larger than the root. In other words, the left child of a node is smaller than itself and the right one is greater than itself.

In this image, the root contains integer 12. All the integers to the left of the root are smaller than 12. Similarly, the numbers to the right are larger than 12. In the second row, consider node 8. Which has left child containing number 5 (smaller than 8) and right child containing 9 (larger than 8).

Categories on the basis of arrangement of the nodes

Perfectly Balanced Tree : A tree which has equal number of nodes on the both sides of the root.

Skewed BST : A tree which doesn't have equal number of nodes on both sides of the root. A tree may be left or right skewed.

The height of a tree is
                                              h = lg(n+1) - 1

where,
h : height of the tree
lg : log base 2
n : number of nodes


In the next post, I'll explain a BST with a code example. 👍
Thank you for reading and if any questions, comment below! 😊😇