What is a Binary Search Tree?

A Binary Search Tree is a tree data structure in which all the nodes follow these properties.

The value of the key of the left sub-tree is less than the value of its parent (root) node’s key.
The value of the key of the right sub-tree is greater than or equal to the value of its parent (root) node’s key.

So in this article, you will learn about Binary Search Trees and how these can be used in a lot of programming problems. Let’s dive…😎

Representation

You can observe the anatomy of the Binary Search Tree from the below image. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.

curtesy: datagrid.com

Basic Operations

Several operations can be done with a BST. The following are the basic operations.

Search − Searches an element in a tree.
Insert − Inserts an element in a tree.
Pre-order Traversal − The root node is visited first, then the left subtree, and finally the right subtree.
In-order Traversal − In this traversal method, the left subtree is visited first, then the root, and later the right sub-tree. We should always remember that every node may represent a subtree itself.
Post-order Traversal − In this traversal method, the root node is visited last, hence the name. First, we traverse the left subtree, then the right subtree, and finally the root node.

Node

We always have to define a node having some data, references to its left and right child nodes.

struct node {
     int data;   
     struct node *leftChild;
     struct node *rightChild;
    };

Search Operation

Whenever an element is to be searched, we have to start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the algorithm for each node.

Algorithm

If root == NULL 
    return NULL;
If number == root->data 
    return root->data;
If number < root->data 
    return search(root->left)
If number > root->data 
    return search(root->right)

Insert Operation

Whenever an element is to be inserted, first we have to locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

If node == NULL 
    return createNode(data)
if (data < node->data)
    node->left  = insert(node->left, data);
else if (data > node->data)
    node->right = insert(node->right, data);  
return node;

Let’s find the node with the minimum value in a Binary Search Tree

This is procedure is quite simple. Just traverse the node from root to left recursively until left is NULL. The node whose left is NULL is the node with minimum value. But at the beginning, you have to create the node and insert the function. What is the minimum value of the following BST?

figure01

Let's find

/Find the minimum value node in Binary Search Tree -- @PulsaraSandeepa

class Node {
  int data;
  Node left, right;

  //constructor assign data to the new node, set left and right children to null
  Node(int data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {

  Node insert(Node node, int data) {
    /* 1. If the tree is empty, return a new,      
         single node */
    if (node == null) {
      return (new Node(data));
    } else {
      // 2. Otherwise, recur down the tree
      if (data <= node.data) {
        node.left = insert(node.left, data);
      } else {
        node.right = insert(node.right, data);
      }
      return node;
    }
  }

  //method to find the min value of BST
  int minvalue(Node node) {
    Node current = node;

    while (current.left != null) {
      current = current.left;
    }
    return (current.data);
  }

  public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();

    //represent the root of BST
    //setting empty tree with null address
    Node root = null;

    root = tree.insert(root, 10);
    tree.insert(root, 8);
    tree.insert(root, 11);
    tree.insert(root, 2);
    tree.insert(root, 14);
    tree.insert(root, 1);
    tree.insert(root, 6);
    tree.insert(root, 16);
    tree.insert(root, 13);
    tree.insert(root, 4);
    tree.insert(root, 3);
    tree.insert(root, 5);

    System.out.println("Minimum value of BST is " + tree.minvalue(root));
  }
}

Conclusion

Now that you have read this article, you should be able to understand the solution by going through this code. It is now your time to practice the problems that use greedy algorithms. It will be a great step in your problem-solving knowledge. Here are some problems that can brush up on your knowledge.

Check if a given array can represent Preorder Traversal of Binary Search Tree

Lowest Common Ancestor in a Binary Search Tree

A program to check if a binary tree is BST or not

Find kth smallest element in BST (Order Statistics in BST)

Check if each internal node of a BST has exactly one child

Let’s meet with another interesting article shortly😊.

References

tutorialspoint.com/data_structures_algorith..

geeksforgeeks.org/binary-tree-data-structure

pulsara's blog