Binary Search Tree (BST)

Definition and Properties of Binary Search Trees

• Definition: A Binary Search Tree (BST) is a node-based binary tree data structure that can either be empty or satisfy strict ordering constraints among its elements.
• Core Properties:
  • Node Values: Every node in the tree contains a value (also referred to as a key).
  • Uniqueness: No two nodes in a Binary Search Tree can share the same value (all keys must be unique).
  • Left Subtree Property: For any given node, all key values in its left child or left subtree must be strictly less than the key value of the parent node ($\text{key}_{\text{left}} < \text{key}_{\text{root}}$).
  • Right Subtree Property: For any given node, all key values in its right child or right subtree must be strictly greater than the key value of the parent node ($\text{key}_{\text{right}} > \text{key}_{\text{root}}$).

• Structural Layout of the Example BST:
  • Root Node: Contains key value $50$.
  • Left Subtree of Node 50: Rooted at key $25$.
    • Left child of $25$ is key $20$, which has a left child with key $10$.
    • Right child of $25$ is key $40$, which has a left child with key $30$ and a right child with key $45$.
  • Right Subtree of Node 50: Rooted at key $75$.
    • Left child of $75$ is key $60$, which has a right child with key $65$.
    • Right child of $75$ is key $80$, which has a right child with key $85$.

Insertion in Binary Search Tree

• Insertion Process Overview:

  • The insertion operation places a new key into the BST while continuously maintaining the Binary Search Tree ordering properties.
  • The operation is performed in two sequential steps:
    1. Search Step: Search the tree recursively or iteratively to locate the appropriate empty position (NULL pointer) where the new node belongs.
    2. Insertion Step: Allocate and insert the new node into the identified position.

• Insertion Algorithm Pseudocode:

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;

• Source Code Implementation (Java):

```java // Create a node class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } } class BST_Insertion { static Node insert(Node root, int key) { if (root == null) return new Node(key); if (root.key == key) return root; if (key < root.key) root.left = insert(root.left, key); else root.right = insert(root.right, key); return root; } // Function to do inorder tree traversal static void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(root.key +