9/17/11

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.

SHARE THIS POST:

Related Posts:

  • HeapSort ( array Based) implementation in Java There are two types of heaps. First one is Max heap and second one is Min heap. Heap (Max/Min) is a special type of binary tree.The roots of  the max heap is greater than its child roots. Other heap is Min heap it is al… Read More
  • Minimax Algorithm Tutorial There are plenty of application in AI but games are the most important thing in today's world and nowadays every OS comes with two player games like chess, checkers etc. So there are algorithm that help to design these ga… Read More
  • Counting Sort Algorithm with Example After a long interval of time I am writing a post on ALGORITHMS. After writing posts on Heap Sort, Merge Sort and Insertion Sort, I decided to write on Counting Sort. Counting sort is an algorithm for sorting a collection … Read More
  • 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-… Read More
  • Algorithm Tutorials - Part 1 : Ad-Hoc Problems I will start with the very basic of Algorithms. Before moving on to the different algorithms, let's first see what does an algorithm actually mean? Definition :  A process or set of rules to be followed i… Read More

1 comment:

  1. Arpit MandliyaJuly 24, 2017 at 4:15 AM

    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.

    ReplyDelete