Searching

Binary search tree

Pinterest LinkedIn Tumblr

A binary search tree is a binary tree (contains only two nodes). The left subtree node data value is less than or equal to parent node data value and right subtree node data value is greater than or equal to parent node data value.

Each node has a unique key which helps to identify the node. The binary search tree supports search, insert and delete the node. It increases memory dynamically.

Traversal:

The Binary search tree supports inorder, preorder and post order traversal.

In-order traversal

Inorder traversal traverse left subtree, display the data and traverse the right subtree. It always gives a sorted sequence of the values

Pre-order traversal

Pre order displays the data, traverse left subtree and traverse the right subtree

Post-order traversal

Post order traverse left subtree, traverse the right subtree and display the data

Search:

Binary search Tree can use recursive or iterative search. Search operation takes time proportional to the tree’s height.

source Code

package com.dsacode.Algorithm.search;
 
class TreeNode {
    public TreeNode left;
    public TreeNode right;
    int data;
 
    public TreeNode(int data) {
        this.left = null;
        this.right = null;
        this.data = data;
    }
}
 
public class BinarySearchTree {
    public TreeNode root;
 
    public BinarySearchTree() {
        root = null;
    }
 
    void printTree(TreeNode node) {
        if (node == null)
            return;
 
        printTree(node.left);
        System.out.print(node.data + "  ");
        printTree(node.right);
    }
 
 
     
    public TreeNode insert(TreeNode node, int data) {
        if (node == null) {
            node = new TreeNode(data);
        } else {
            if (data <= node.data) {
                node.left = insert(node.left, data);
            } else {
                node.right = insert(node.right, data);
            }
        }
 
        return (node);
    }
     
 
    public boolean search(TreeNode node, int value) {
 
        if (value == node.data)
              return true;
        else if (value < node.data) {
              if (node.left == null)
                    return false;
              else
                    return search(node.left,value);
        } else if (value > node.data) {
              if (node.right == null)
                    return false;
              else
                   return search(node.right,value);
 
        }
 
        return false;
 
  }
         
         
    public static void main(String[] args) {
        BinarySearchTree b = new BinarySearchTree();
 
        b.root = new TreeNode(2);
        b.root.left = new TreeNode(1);
        b.root.right = new TreeNode(3);
        b.root.right.right = new TreeNode(4);
        b.insert(b.root.right.right, 5);
        System.out.print("All Binary Tree Values: ");
        b.printTree(b.root);
        System.out.println();
         
        if(b.search(b.root, 4)==true)
            System.out.println("Value '4' fond from given tree!");
        else
            System.out.println("Value '4' Not fond from given tree!");
         
        if(b.search(b.root, 11)==true)
            System.out.println("Value '11' fond from given tree!");
        else
            System.out.println("Value '11' not fond from given tree!");
    }
}

Output

All Binary Tree Values: 1 2 3 4 5 
Value '4' found from given tree!
Value '11' not found from given tree!

Algorithm Explanation

Check the key with current root node value. If the value is equal, return the value
If the search key is less than the root node value, search in the left sub-tree. If it does not have left sub-tree return as null.
If the search key is greater than the root node value, search in the right subtree. If the tree does not contain right sub-tree returns as null.

Time Complexity

Best CaseAverage CaseWorst Case
O(n)O(log n)O(n)

Reference

  1. https://www.cs.usfca.edu/~galles/visualization/BST.html
  2. http://en.wikipedia.org/wiki/Binary_search_tree

Write A Comment