binary search tree java code example

Example 1: binary search java

// Java implementation of iterative Binary Search 
class BinarySearch { 
	// Returns index of x if it is present in arr[], 
	// else return -1 
	int binarySearch(int arr[], int x) 
	{ 
		int l = 0, r = arr.length - 1; 
		while (l <= r) { 
			int m = l + (r - l) / 2; 

			// Check if x is present at mid 
			if (arr[m] == x) 
				return m; 

			// If x greater, ignore left half 
			if (arr[m] < x) 
				l = m + 1; 

			// If x is smaller, ignore right half 
			else
				r = m - 1; 
		} 

		// if we reach here, then element was 
		// not present 
		return -1; 
	} 

	// Driver method to test above 
	public static void main(String args[]) 
	{ 
		BinarySearch ob = new BinarySearch(); 
		int arr[] = { 2, 3, 4, 10, 40 }; 
		int n = arr.length; 
		int x = 10; 
		int result = ob.binarySearch(arr, x); 
		if (result == -1) 
			System.out.println("Element not present"); 
		else
			System.out.println("Element found at "
							+ "index " + result); 
	} 
}

Example 2: binary search tree insert java

public static Node insert(Node root, int x){
    if (root == null)
        return new Node(x);
    else if(x>root.getData())
        root.setRightChild(insert(root.getRightChild(),x));
    else
        root.setLeftChild(insert(root.getLeftChild(),x));
    return root;
}

Example 3: binary search java

binary search program in java.
public class BinarySearchExample
{
   public static void binarySearch(int[] arrNumbers, int start, int end, int keyElement)
   {
      int middle = (start + end) / 2;
      while(start <= end)
      {
         if(arrNumbers[middle] < keyElement)
         {
            start = middle + 1;
         }
         else if(arrNumbers[middle] == keyElement)
         {
            System.out.println("Element found at index: " + middle);
            break;
         }
         else
         {
            end = middle - 1;
         }
         middle = (start + end) / 2;
      }
      if(start > end)
      {
         System.out.println("Element not found!");
      }
   }
   public static void main(String[] args)
   {
      int[] arrNumbers = {14,15,16,17,18};
      int keyElement = 16;
      int end = arrNumbers.length - 1;
      binarySearch(arrNumbers, 0, end, keyElement);
   }
}

Example 4: java binary tree

public class BinaryTree {

    private int key;

    private BinaryTree left, right;

    /**
     * Simple constructor.
     *
     * @param key
     *     to set as key.
     */
    public BinaryTree(int key) {
        this.key = key;
    }

    /**
     * Extended constructor.
     *
     * @param key
     *     to set as key.
     * @param left
     *     to set as left child.
     * @param right
     *     to set as right child.
     */
    public BinaryTree(int key, BinaryTree left, BinaryTree right) {
        this.key = key;
        setLeft(left);
        setRight(right);
    }

    public int getKey() {
        return key;
    }

    /**
     * @return the left child.
     */
    public BinaryTree getLeft() {
        return left;
    }

    /**
     * @return the right child.
     */
    public BinaryTree getRight() {
        return right;
    }

    public boolean hasLeft() {
        return left != null;
    }

    public boolean hasRight() {
        return right != null;
    }

    //Return a String representation of the BinaryTree using level order traversal
    public String toString(){
        int h = height(this);
        int i;
        String result = "";
        for (i=1; i<=h; i++) {
            result += printGivenLevel(this, i);
        }
        return result;
    }

    //returns the number of nodes in the BinaryTree
    public int size(){
        return size(this);
    }

    public static int size(BinaryTree tree){
        if(tree == null) return 0;
        return 1 + size(tree.getLeft()) + size(tree.getRight());
    }

    public int height(){ return height(this);}

    public static int height(BinaryTree tree){
        if(tree == null) return 0;
        int left = height(tree.getLeft());
        int right = height(tree.getRight());
        return Math.max(left, right) + 1;
    }

    public String printGivenLevel (BinaryTree root ,int level) {
        if (root == null) return "";
        String result = "";
        if (level == 1) {
            result += root.getKey() + " ";
            return result;
        }else if (level > 1) {
            String left = printGivenLevel(root.left, level-1);
            String right = printGivenLevel(root.right, level-1);
            return left + right;
        }else{
            return "";
        }
    }

    /**
     * @param left
     *     to set
     */
    public void setLeft(BinaryTree left) {
        this.left = left;
    }

    /**
     * @param right
     *     to set
     */
    public void setRight(BinaryTree right) {
        this.right = right;
    }
}

Example 5: binary tree search

/* This is just the seaching function you need to write the required code.
	Thank you. */

void searchNode(Node *root, int data)
{
    if(root == NULL)
    {
        cout << "Tree is empty\n";
        return;
    }

    queue<Node*> q;
    q.push(root);

    while(!q.empty())
    {
        Node *temp = q.front();
        q.pop();

        if(temp->data == data)
        {
            cout << "Node found\n";
            return;
        }

        if(temp->left != NULL)
            q.push(temp->left);
        if(temp->right != NULL)
            q.push(temp->right);
    }

    cout << "Node not found\n";
}

Example 6: insert binary search tree

void BSNode::insert(std::string value) {

	if (this->_data == value) {
		_count++;
		return;
	}

	if (this->_data > value) {
		if (this->getLeft() == nullptr) {
			this->_left = new BSNode(value);
		}
		this->getLeft()->insert(value);
		return;
	}

	if (this->getRight() == nullptr) {
		this->_right = new BSNode(value);
		return;
	}
	this->getRight()->insert(value);
}

Tags:

Java Example