Binary Search Trees

A binary search tree (BST), also known as an ordered or sorted binary tree, is a type of binary tree with the following properties:

• The value of each node in the left subtree is less than or equal to the value of the node.
• The value of each node in the right subtree is greater than the value of the node.
• The left and right subtrees are also binary search trees.

This ordering of nodes allows for efficient search, insert, and delete operations.

Here's an example of a binary search tree:

1        50
2       /  \
3     30    70
4    / \   / \
5  20  40  60  80

In the example above, the left subtree of the root node (50) contains values less than 50, and the right subtree contains values greater than 50.

Inserting into a Binary Search Tree

To insert a value into a binary search tree, we compare the value with the current node. If the value is less than the current node, we go left; if it is greater, we go right. We continue this process until we reach a null node, and then we create a new node with the value at that position.

Here's the Java code for inserting a value into a binary search tree:

xxxxxxxxxx

}

public class BinarySearchTree {

  class Node {

    int key;

    Node left, right;

​

    public Node(int item) {

      key = item;

      left = right = null;

    }

  }

​

  Node root;

​

  public BinarySearchTree() {

    root = null;

  }

​

  public void insert(int key) {

    root = insertRec(root, key);

  }

​

  private Node insertRec(Node root, int key) {

    if (root == null) {

      root = new Node(key);

      return root;

    }

​

    if (key < root.key) {

      root.left = insertRec(root.left, key);