Binary Search Tree is a data structure in which the given tree is structured in such a way that the left child node is always less than the parent node and the parent node is always less than the right child node.
In this tutorial we will see how to find an element with any given target value.
First we create a node with data and left and right pointers which will help us store information about any given node's two children node.
public class Node {
public int element; // The data in the node
public Node left; // Left child
public Node right; // Right child
public Node(int element, Node left, Node right) {
this.element = element;
this.left = left;
this.right = right;
}
}
This problem is a perfect example for recursive programming.
In order to find the any element in a BST, we have to understand that smaller values always resides on the most left side of the tree and greater values on the right side of the tree.
To find the given target value, we can start from the root, if we the root node is equal to target then we can return true.
Otherwise check if target is smaller than the root, if so then we can keep looking on the left side of the tree.
Else if target is greater than the root, then we can keep looking on the right side of the tree.
public bool find(int x) {
return find(x, root);
}
private bool find(int x, Node n) {
if (n == null) return false;
if (n != null && n.element==x)//if it found on the root
return true;
return ((x - n.element) < 0) ? find(x, n.left) : find(x, n.right);//binary search
}