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.



Post a Comment