How would you search in a Binary Search Tree?

The search in a Binary Search Tree would happen on the Binary search algorithm since the data in a BST is sorted. You enter the search through the root node and depending on if the search value is greater than or smaller than the root value you would move down the right or the left tree. You can search this recursively as explained in the example below.

class TreeNode{
  int value;
  TreeNode left;
  TreeNode right;

  public TreeNode(int x){
	value=x;
  }

  public static TreeNode search(int key, TreeNode n){
	if (n != null){
	  if (n.value == key)
		return n;
	  else{
		if (key > n.value){
		  return search(key, n.right);
		}
		else{
		  return search(key, n.left);
		}
	  }
	}
	else{
	  return null;
	}
  }
  
  @Override
  public String toString() {
	return "Node value is "+value;
  }
}

 

Test code is as follows

public class BSTUtil {
  public static void main(String[] args) {
	TreeNode root=new TreeNode(8);
	TreeNode.insert(root, new TreeNode(3));
	TreeNode.insert(root, new TreeNode(10));
	TreeNode.insert(root, new TreeNode(6));
	TreeNode.insert(root, new TreeNode(1));
	TreeNode.insert(root, new TreeNode(14));
	TreeNode.insert(root, new TreeNode(4));
	TreeNode.insert(root, new TreeNode(7));
	TreeNode.insert(root, new TreeNode(13));
	
	System.out.println(TreeNode.search(13, root));
	System.out.println(TreeNode.search(54, root));
  }
}

The tree after creation will look something like this

Output of the test code will be

Node value is 13
null

 

core java 12

FOLLOW US ON LinkedIn



Explore Tutu'rself