Binary Search Tree : Basics

A Binary Tree is a tree data structre in which each node has atmost two child nodes, usually called as 'left' and  'right' child respectively. 
Binary Tree

A binary tree which satisfies the 'binary-search-tree property' is a Binary Search Tree. Apart from having the child nodes ie 'left child' and 'right child' the binary search tree also has key (element stored inside the node).The Binary Search tree property is :

Let x be a node in a binary tree. If y is a node in the left subtree of x, then y.key <= x.key. If y is a node in the right of the subtree of x, then y.key >= x.key. 

The height of the Binary Search Tree equals the number of links from the root node to the deepest node.

Binary Search Tree
In the above figure, the key of the root node is 8 and you can see that the left child key is '3' i.e. less than 8 and the right child key is '10' which is greater than 8. If you go down the left and right subtree respectively you will find that the binary search tree property is satisfied by the above tree.

Now we are ready to move on to Binary Search Tree Operations Tutorial.


1 comment:

  1. Great post, Your post provides relevant and fruitful information about binary search tree with suitable diagram. This information is very helpful, especially for the beginners. Binary search tree is a data structure that is used to organize the data in a sorted manner. Binary search tree is mainly used in searching and sorting applications. A tree is called binary search tree if it posses properties: 1. Each node has no more than two children. 2. Every node must contain leaf node or another binary search tree. 3. Left sub tree must contain only nodes with keys less than its parent node. 4. Right sub tree must contain only nodes with keys greater than its parent node.