Insert Operation in Binary Search Trees

Understanding the Insert Operation

Insertion in a binary search tree (BST) involves adding a new node while maintaining the BST property: for each node, all elements in its left subtree are less than the node's value, and all elements in its right subtree are greater than the node's value.

Insertion Algorithm

The insertion algorithm follows these steps:

1. If the tree is empty, create a new node and make it the root.
2. Otherwise, compare the new value with the current node's value.
3. If the new value is less than the current node's value, recursively insert into the left subtree. If the left child is null, create a new node and make it the left child.
4. If the new value is greater than the current node's value, recursively insert into the right subtree. If the right child is null, create a new node and make it the right child.
5. If the value already exists in the tree, you can either update it or ignore the insertion.

Implementation

Here's how we implement the insert operation in TypeScript:

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;
 
  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
 
class BinarySearchTree {
  root: TreeNode | null;
 
  constructor() {
    this.root = null;
  }
 
  insert(value: number): void {
    const newNode = new TreeNode(value);
 
    if (this.root === null) {
      this.root = newNode;
      return;
    }
 
    const insertNode = (node: TreeNode, newNode: TreeNode): void => {
      if (newNode.value < node.value) {
        if (node.left === null) {
          node.left = newNode;
        } else {
          insertNode(node.left, newNode);
        }
      } else if (newNode.value > node.value) {
        if (node.right === null) {
          node.right = newNode;
        } else {
          insertNode(node.right, newNode);
        }
      }
    };
 
    insertNode(this.root, newNode);
  }
}

Example

Let's see how insertion works with an example:

1. Start with an empty tree and insert 10. This becomes the root.
2. Insert 5. Since 5 < 10, it becomes the left child of 10.
3. Insert 15. Since 15 > 10, it becomes the right child of 10.
4. Insert 3. Since 3 < 10 and 3 < 5, it becomes the left child of 5.
5. Insert 7. Since 7 < 10 but 7 > 5, it becomes the right child of 5.
6. Insert 12. Since 12 > 10 but 12 < 15, it becomes the left child of 15.
7. Insert 18. Since 18 > 10 and 18 > 15, it becomes the right child of 15.

The resulting tree would look like:

        10
       /  \
      5    15
     / \  / \
    3   7 12 18

Time and Space Complexity