Binary Search Tree

A binary search tree (BST) is a binary tree in a symmetric order, where each node has a key (and an associated value). A binary tree means it consists of nodes, and each node has at most two children(left and right child).

While being in a symmetric order is that every node is larger than all the nodes in the left subtree, and smaller than the keys in the right subtree.

It’s used to implement the symbol tables (associative arrays), and it’s the key that would be used to sort the nodes accordingly.

Binary Search Tree (BST) with Example

A Binary Search Tree is a binary tree data structure that satisfies the BST property. Each node in a BST has a unique key or value and two children, commonly referred to as the left child and the right child. The BST property dictates that for any given node, all the keys in the left subtree are less than the key at the node itself, while all the keys in the right subtree are greater.

The key property of a BST is that it allows for efficient searching, insertion, and deletion operations with a time complexity of O(log n) on average and O(n) in the worst-case scenario. This property makes it an excellent choice for dynamic data structures, where data is frequently updated and needs to be quickly retrieved.

BST Operations

Searching: The search operation is the cornerstone of BSTs. To find a specific value in the tree, we start at the root and traverse through the tree, comparing the target value with the current node's value. If the value is less than the current node's value, we move to the left subtree; otherwise, we move to the right subtree. This process continues until we find the desired value or determine that it doesn't exist in the tree.
Insertion: To insert a new element into a BST, we perform a search to find the appropriate position to insert the new node while maintaining the BST property. If the value already exists in the tree, we can either reject the insertion or handle duplicates according to the specific implementation.
Deletion: Deleting a node from a BST requires careful consideration to maintain the BST property. The process involves handling three different cases: a node with no children, a node with one child, and a node with two children. The replacement of the deleted node must preserve the BST structure.

Traversing nested trees

Advantages of Binary Search Trees

Efficient Searching: As mentioned earlier, the BST property allows for rapid searching, making it ideal for use in searching algorithms like binary search, where data needs to be located swiftly.
Sorted Order: In-order traversal of a BST provides a sorted sequence of elements, making it easier to perform range queries or obtain sorted results from the tree.
Dynamic Operations: BSTs offer efficient dynamic operations, such as insertion and deletion, without requiring the tree's complete reconstruction.
Memory Efficiency: BSTs consume memory proportional to the number of elements in the tree. Unlike other data structures like arrays
Limitations and Balancing

Despite their many advantages, BSTs can exhibit performance issues in certain scenarios. For instance, a degenerate BST with skewed height can result in O(n) time complexity for search, making it no better than a linear search.

To address this, various balancing techniques have been developed to maintain the height balance of BSTs. Some popular self-balancing BSTs include AVL trees, Red-Black trees, and Splay trees. These techniques ensure that the tree remains balanced, providing optimal search and dynamic operation performance.

Tree traversal refers to the process of visiting all nodes in a tree data structure in a systematic manner. There are different methods to traverse a tree, such as depth-first traversal (in-order, pre-order, and post-order) and breadth-first traversal. Below are examples of how to implement these tree traversal algorithms in JavaScript.

Assume you have a binary tree with the following structure:

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

Insertion and Deletion in a Binary search tree

In a Binary Search Tree (BST), insertion and deletion are essential operations that maintain the binary search tree property. Here's how you can implement insertion and deletion in a Binary Search Tree using JavaScript.

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  // Helper function to insert a node recursively
  _insertNode(currentNode, data) {
    if (data < currentNode.data) {
      if (currentNode.left === null) {
        currentNode.left = new Node(data);
      } else {
        this._insertNode(currentNode.left, data);
      }
    } else {
      if (currentNode.right === null) {
        currentNode.right = new Node(data);
      } else {
        this._insertNode(currentNode.right, data);
      }
    }
  }
// Insert a value into the BST
  insert(data) {
    if (this.root === null) {
      this.root = new Node(data);
    } else {
      this._insertNode(this.root, data);
    }
  }

  // Helper function to find the minimum node in a subtree
  _findMinNode(node) {
    while (node.left !== null) {
      node = node.left;
    }
    return node;
  }

  // Helper function to delete a node recursively
  _deleteNode(currentNode, data) {
    if (currentNode === null) {
      return null;
    }
if (data < currentNode.data) {
      currentNode.left = this._deleteNode(currentNode.left, data);
    } else if (data > currentNode.data) {
      currentNode.right = this._deleteNode(currentNode.right, data);
    } else {
      // Case 1: Node with only one child or no child
      if (currentNode.left === null) {
        return currentNode.right;
      } else if (currentNode.right === null) {
        return currentNode.left;
      }

      // Case 2: Node with two children
      const minRightSubtree = this._findMinNode(currentNode.right);
      currentNode.data = minRightSubtree.data;
      currentNode.right = this._deleteNode(currentNode.right, minRightSubtree.data);
    }

    return currentNode;
  }
// Delete a value from the BST
  delete(data) {
    this.root = this._deleteNode(this.root, data);
  }
}

// Example usage:
const bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);

console.log("Original BST:");
console.log(JSON.stringify(bst, null, 2));

bst.delete(30);
console.log("BST after deleting 30:");
console.log(JSON.stringify(bst, null, 2));

In this implementation, the _insertNode function recursively finds the appropriate position to insert a new node based on the value being inserted. The _deleteNode function recursively finds the node to delete and handles three cases: deleting a node with no children, deleting a node with one child, and deleting a node with two children (by replacing it with the minimum node from its right subtree).

Depth-First Traversals:

In-Order Traversal: Visits the left subtree, then the root, and finally the right subtree.

function inOrderTraversal(node) {
  if (node !== null) {
    inOrderTraversal(node.left);
    console.log(node.value);
    inOrderTraversal(node.right);
  }
}

// Example usage:
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

inOrderTraversal(root); // Output: 4, 2, 5, 1, 3

Assume you have a binary tree with the following structure:

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

Pre-Order Traversal: Visits the root, then the left subtree, and finally the right subtree.

function preOrderTraversal(node) {
  if (node !== null) {
    console.log(node.value);
    preOrderTraversal(node.left);
    preOrderTraversal(node.right);
  }
}

// Example usage:
preOrderTraversal(root); // Output: 1, 2, 4, 5, 3

Post-Order Traversal: Visits the left subtree, then the right subtree, and finally the root.

function postOrderTraversal(node) {
  if (node !== null) {
    postOrderTraversal(node.left);
    postOrderTraversal(node.right);
    console.log(node.value);
  }
}

// Example usage:
postOrderTraversal(root); // Output: 4, 5, 2, 3, 1

Breadth-First Traversal:

Breadth-first traversal also known as "level order traversal", visits all nodes on the same level before moving to the next level.

function breadthFirstTraversal(root) {
  if (!root) return;

  const queue = [];
  queue.push(root);

  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node.value);

    if (node.left) {
      queue.push(node.left);
    }
if (node.right) {
      queue.push(node.right);
    }
  }
}

// Example usage:
breadthFirstTraversal(root); // Output: 1, 2, 3, 4, 5

breadth-First Search

The breadthFirstSearch method takes a starting vertex as an argument and explores the graph using the BFS algorithm. It starts by adding the starting vertex to the visited set and enqueueing it to the queue. Then it repeatedly dequeues a vertex from the front of the queue, processes it (e.g., prints it), and adds all its unvisited neighbors to the queue and visited set.

class Graph {
  constructor() {
    this.vertices = new Map();
  }

  addVertex(vertex) {
    this.vertices.set(vertex, []);
  }

  addEdge(fromVertex, toVertex) {
    this.vertices.get(fromVertex).push(toVertex);
    this.vertices.get(toVertex).push(fromVertex); // For an undirected graph
  }
 breadthFirstSearch(startingVertex) {
    const visited = new Set();
    const queue = [];

    visited.add(startingVertex);
    queue.push(startingVertex);

    while (queue.length !== 0) {
      const currentVertex = queue.shift();
      console.log(currentVertex); // Do whatever operation you want with the vertex (e.g., push into result array)

      const neighbors = this.vertices.get(currentVertex);
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
    }
      }
    }
  }
}

// Example usage:
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'D');
graph.addEdge('D', 'E');
graph.breadthFirstSearch('A'); // Output: A, B, C, D, E

Methods of Search

-> The main difference between Breadth First search and Depth First search is that BFS uses a queue whereas DFS uses a stack.

Choose the appropriate traversal method based on your requirements for processing the nodes in the tree.

In conclusion, the binary search tree (BST) stands as a fundamental and powerful data structure that has proven to be invaluable in a wide range of applications.

BSTs provide a balanced and organized way to store data, ensuring that search operations can be performed in O(log n) time complexity in the average case, making them highly efficient. However, it is essential to maintain their balance to avoid worst-case scenarios, such as skewed trees, which could degrade performance to O(n).

Moreover, we have discussed how the properties of BSTs, such as maintaining the left-child smaller and right-child larger, facilitate sorting and allow for in-order traversal, providing an ordered representation of the data.

While the BST offers many advantages, it is essential to remember that its performance relies heavily on data distribution.

Uzma's Blog