Searching in a Binary Search Tree in Java

Now that we have a working version of a binary search tree fully implemented in Java, lets go a step ahead and start analyzing that piece of code.

Binary search tree is a data structure which has the following public methods exposed

public void add(int data);
public boolean search(int searchData);
public void printOrdered();

Ofcourse, the above three methods are not the only methods present in a binary search tree, but once these methods are understood and analyzed, understanding the rest of the binary tree should not be a big problem.

Adding elements to a binary tree : In the example program that I've written, I am using only integers as the node data to hold values and ofcourse you need something that is comparable to make binary search trees realistic (refer my previous post on comparable objects). While adding data to a binary search tree, we need to follow the simple rule - lesser should go left and greater then or equal should go to the right of the parent node. By taking a snap at the code, the add(int data) method internally calls a private method that does the job in recursion.

Searching elements in a tree : Searching elements in any data structure is a essential part that reflects the space and time complexity and Binary search tree is no exception. To search from a balanced binary search tree, it would take only O(logn) whereas the same is not so in case of an Array. The simple reason being, for arrays, we need to traverse the entire array sequentially in which the worst case would produce O(n). Consider the below example where in we need to search the element 5.

Whereas in a binary search, the depth count would simply provide the desired result.
Consider a situation in a balanced binary search tree of 7 elements, when the value given to search is at its leaf (which would be the worst case here). The example shown below is a balanced and a perfect binary search tree (which we would look into future posts). Assume the element we need to find is 5. First inspect the root (4), our value is greater, so go the right node, then inspect it (6), our value is lesser so go the left node, bingo! we found our result. This took only 2 comparisons of a tree of depth 2 whereas it look 7 comparisons in an array of length 7! Through this we can come to conclusion that binary trees perform search in O(logn) time.

The method printOrdered() is something we have to allocate time and look into a different post. As for now, lets convince ourselves that binary tree's search is powerful enough to perform the search operation in O(logn) time.
Rest, later. Cheers,
Bragaadeesh.