Photo by Jeremy Bishop on Unsplash

Binary Search And Trees in Javascript

The best way to learn is to teach! 😊

In this article series, we’ll explore different algorithms using data structures in JavaScript. To kick things off, I thought it would be great to start with binary search and binary search trees — terms that many of us are likely already familiar with. The reason I want to explain them together is that, while they share similar names, they’re actually two distinct concepts, and they often get mixed up.

I’ll start with a quick introduction to each and then share some sample code. As always, please feel free to reach out if you have any questions or suggestions. I’m here to help, and I’d love to hear from you. Happy coding and good luck!

Binary Search

Binary search is an efficient algorithm used to find the position of a target element within a sorted array. Binary search only works when your list is in the sorted order.

The concept behind binary search is to continually divide the search space in half until you either find the target value or determine that it doesn’t exist in the array. This approach significantly reduces the number of elements that need to be checked compared to a linear search.

For example, consider a sorted list of numbers ranging from 100 to 1. Instead of going one by one, binary search cuts the list roughly in half each time:

100 -> 50 -> 25 -> 13 -> 7 -> 4 -> 2 -> 1

With each step, the search narrows down, reducing the possible search space.

In a linear search, the maximum number of guesses you need to make is equal to the size of the list, as you could end up having to check each element. This approach is said to have “linear time complexity” or O(n), because the time taken grows directly with the size of the input list.

In contrast, binary search operates in “logarithmic time complexity” or O(log n), meaning that with every guess, the number of elements left to search is reduced by half. This makes binary search much faster for large datasets, especially compared to linear search. Instead of taking as many steps as there are elements, binary search takes only log(n) steps, which drastically improves efficiency as the size of the dataset grows.

This efficiency makes binary search a fundamental technique when working with sorted datasets and contributes to its widespread use in computer science.

Binary search uses the principle of divide and conquer to repeatedly divide the search space, making it efficient for finding a target in a sorted dataset.

How Binary Search works:

• start with 2 pointers, low and high, which represent the start of the array and the end of the array.
• find the middle element of the array
• compare the middle element with the target
  - If the middle element matches the target, you’ve found it
  - If the middle element is greater than the target, move the high to the left of the middle element
  - If the middle element is less than the target, move the low to the right of the middle element
• continue narrowing down the search space by adjusting low and high until you find the target or low exceeds high

P.S. You can use websites like this to visualize binary search interactively.

Consider a sorted array: [1, 3, 5, 7, 9, 11, 13], and the target is 9.

• Initial pointers:
  low = 0, high = 6 (array length - 1)
• Calculate mid:
  mid = Math.floor((low + high) / 2) = 3
array[mid] = 7
Since 7 < 9, move low to mid + 1 = 4.
• Calculate the new mid:
  mid = Math.floor((low + high) / 2) = 5
array[mid] = 11
Since 11 > 9, move high to mid - 1 = 4.
• Calculate the new mid:
  mid = Math.floor((low + high) / 2) = 4
array[mid] = 9 which is equal to the target. Found!

function binarySearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);

        if (arr[mid] === target) {
            return mid; // Target found, return the index
        } else if (arr[mid] < target) {
            low = mid + 1; // Look in the right half
        } else {
            high = mid - 1; // Look in the left half
        }
    }

    return -1; // Target not found
}

let array = [1, 3, 5, 7, 9, 11, 13];
let target = 9;
console.log(binarySearch(array, target)); // Output: 4 (index of 9)

Binary Search Trees

A Binary Search Tree (BST) is a specific type of binary tree in which each node has at most two children, and all the nodes follow a particular ordering property. The structure of a BST allows for efficient searching, insertion, and deletion operations, typically achieving O(log n) time complexity for these operations, making it highly useful for searching sorted data efficiently.

1. Each node contains a value.
2. The left subtree of a node contains only nodes with values less than the node’s value.
3. The right subtree of a node contains only nodes with values greater than the node’s value.
4. Both the left and right subtrees must also be binary search trees.

Key Operations in a Binary Search Tree

Search: Check if a particular value exists in the tree.
Insertion: Add a new node while maintaining the BST properties.
Deletion: Remove a node while ensuring the remaining tree is still a BST.

Here is an example:
[8, 3, 10, 1, 6, 14, 4, 7, 13]

1. Start with 8 as the root node.
2. Insert 3:
   Since 3 < 8, insert 3 as the left child of 8
3. Insert 10:
   Since 10 > 8, insert 10 as the right child of 8
4. Insert 1:
   1 < 8 and 1 < 3, so insert 1 as the left child of 3
5. Insert 6:
   6 < 8 but 6 > 3, so insert 6 as the right child of 3
6. Insert 14:
   14 > 8 and 14 > 10, so insert 14 as the right child of 10
7. Insert 4:
   4 < 8, 4 > 3, and 4 < 6, so insert 4 as the left child of 6
8. Insert 7:
   7 < 8, 7 > 3, and 7 > 6, so insert 7 as the right child of 6
9. Insert 13:
   13 > 8, 13 > 10, and 13 < 14, so insert 13 as the left child of 14

The resulting Binary Search Tree looks like this:

       8
     /   \
    3    10
   / \     \
  1   6    14
     / \   /
    4  7  13

If you want to search for a value, say 7:

• Start from the root (8):
• 7 < 8, so move to the left child (3).
• 7 > 3, so move to the right child (6).
• 7 > 6, so move to the right child (7).
• You find 7!

P.S. You can use websites like this to visualize binary search interactively.

In BST, tree traversal is the process of visiting each node in a specific order. There are different types of traversal methods, each serving different purposes. The main types are Preorder, Inorder, and Postorder traversal.

Preorder Traversal (Root → Left → Right)

You visit the nodes in the following order:

1. Root node
2. Left subtree
3. Right subtree

This traversal is often used for creating a copy of a tree or when you want to serialize the structure of a tree.

The preorder traversal of this tree would be:
8, 3, 1, 6, 4, 7, 10, 14, 13

function preorderTraversal(node) {
    if (node === null) return;
    console.log(node.val); // Visit the root
    preorderTraversal(node.left); // Traverse the left subtree
    preorderTraversal(node.right); // Traverse the right subtree
}

Inorder Traversal (Left → Root → Right)

You visit the nodes in the following order:

1. Left subtree
2. Root node
3. Right subtree

This type of traversal is particularly useful in binary search trees because it visits the nodes in sorted order (from smallest to largest value).

The inorder traversal would be: 1, 3, 4, 6, 7, 8, 10, 13, 14

function inorderTraversal(node) {
    if (node === null) return;
    inorderTraversal(node.left); // Traverse the left subtree
    console.log(node.val); // Visit the root
    inorderTraversal(node.right); // Traverse the right subtree
}

Postorder Traversal (Left → Right → Root)

You visit the nodes in the following order:

1. Left subtree
2. Right subtree
3. Root node

This traversal is useful for deleting nodes from a tree or evaluating mathematical expressions represented by the tree (where leaf nodes are operands, and internal nodes are operators)**

The postorder traversal would be: 1, 4, 7, 6, 3, 13, 14, 10, 8.

function postorderTraversal(node) {
    if (node === null) return;
    postorderTraversal(node.left); // Traverse the left subtree
    postorderTraversal(node.right); // Traverse the right subtree
    console.log(node.val); // Visit the root
}

Maybe now you wonder why and when we need the binary search tree in real life (like I did 😃)

Why Do We Need Binary Search Trees?

1. Efficient Searching: BSTs are designed to make searching for data efficient. Because of the structure, each time you traverse down a level of the tree, you eliminate half of the remaining possible nodes where the value could exist. This results in a time complexity of O(log n) for search operations if the tree is balanced. This is especially beneficial compared to a linear search through an unsorted list, which takes O(n) time.
2. Sorted Data Structure:
   Unlike arrays or hash tables, BSTs store elements in a way that naturally maintains a sorted order. This means you can easily traverse the tree in an in-order fashion to get elements in ascending order without extra sorting. This property makes BSTs ideal when the order of elements is important for operations like range queries or finding the kth smallest/largest element.
3. Fast Insertions and Deletions:
   BSTs allow insertions and deletions efficiently compared to arrays, especially if the tree remains balanced. Inserting a new value or deleting a value in a balanced BST takes O(log n) time, while inserting or deleting in an array may take O(n) if the element needs to be added at the beginning or middle. This makes BSTs particularly useful for maintaining a dynamic dataset that changes over time (e.g., priority queues, dynamic sets).
4. Dynamic and Scalable:
   Unlike arrays, which have a fixed size, BSTs are dynamic. They grow and shrink as elements are added or removed, which makes them highly suitable for datasets whose size varies over time. This dynamic nature is useful in real-world applications where the number of elements is not known in advance.
5. Key-Value Mapping:
   BSTs can be used to implement maps or dictionaries, where you need a key-value mapping with sorted keys. Self-balancing BSTs (e.g., AVL trees or Red-Black trees) are often used for these cases, ensuring that the tree height remains logarithmic, thus providing efficient operations.

Here is the complete Binary Search Tree code. You can check and try to write by yourself.

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

  //INSERT
  insert(value) {
    const newNode = new Node(value)
    if (this.root === null) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
  }

  insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode
      } else {
        this.insertNode(node.left, newNode)
      }
    } else {
      if (node.right === null) {
        node.right = newNode
      } else {
        this.insertNode(node.right, newNode)
      }
    }
  }

  //SEARCH
  search(value) {
    return this.searchNode(this.root, value)
  }

  searchNode(node, value) {
    if (node === null) {
      return false
    }

    if (value < node.value) {
      return this.searchNode(node.left, value)
    } else if (value > node.value) {
      return this.searchNode(node.right, value)
    } else {
      return true
    }
  }

  //TRAVERSAL
  inorderTraversal(node = this.root, result = []) {
    if (node !== null) {
      this.inorderTraversal(node.left, result)
      result.push(node.value)
      this.inorderTraversal(node.right, result)
    }
    return result
  }
  preorderTraversal(node = this.root, result = []) {
    if (node !== null) {
      result.push(node.value)
      this.preorderTraversal(node.left, result)
      this.preorderTraversal(node.right, result)
    }
    return result
  }

  postorderTraversal(node = this.root, result = []) {
    if (node !== null) {
      this.postorderTraversal(node.left, result)
      this.postorderTraversal(node.right, result)
      result.push(node.value)
    }
    return result
  }

  //DELETE

  delete(value) {
    this.root = this.deleteNode(this.root, value)
  }

  deleteNode(node, value) {
    if (node === null) {
      return null
    }

    if (value < node.value) {
      node.left = this.deleteNode(node.left, value)
    } else if (value > node.value) {
      node.right = this.deleteNode(node.right, value)
    } else {
      //case1: node has no childeren
      if (node.left === null && node.right === null) {
        return null
      }
      //case2: node has only one childeren
      if (node.left === null) {
        return node.right
      } else if (node.right === null) {
        return node.left
      }
      //case3: node has two childeren

      let minRightNode = this.findMinNode(node.right)
      node.value = minRightNode.value

      node.right = this.deleteNode(node.right, minRightNode.value)
    }

    return node
  }

  findMinNode(node) {
    while (node.left !== null) {
      node = node.left
    }
    return node
  }
}

const bst = new BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(3)
bst.insert(7)
bst.insert(23)
bst.insert(12)
bst.insert(13)

console.log("In-order traversal: ", bst.inorderTraversal())
console.log("Search for 7: ", bst.search(7))
console.log("Search for 20: ", bst.search(20))

bst.delete(12)
console.log("In-order traversal: ", bst.inorderTraversal())
console.log("Pre-order traversal: ", bst.preorderTraversal())
console.log("Post-order traversal: ", bst.postorderTraversal())

Notes

** Let’s dive deeper into why postorder traversal is particularly useful for deleting nodes from a tree and for evaluating mathematical expressions represented by the tree.
When deleting nodes from a binary tree, postorder traversal is the most effective traversal method because:

• In postorder traversal, you visit the left subtree first, then the right subtree, and finally the root node.
• This means that for each subtree, you traverse and delete its children nodes before deleting the parent node.

This order ensures that, when deleting a tree, all descendants of a node are deleted before the node itself is deleted, which is crucial to avoid losing access to children nodes while trying to delete a parent node first.

A mathematical expression tree is a tree that represents an arithmetic expression:

• Leaf nodes represent operands (such as numbers or variables).
• Internal nodes represent operators (such as +, -, *, or /).

The purpose of using postorder traversal for evaluating mathematical expressions is to follow the order of operations correctly, like evaluating the components of an expression from the bottom up.

        *
       / \
      +   -
     / \  / \
    4  5 7  2

• Step 1: Start from the left subtree rooted at +
Traverse left: 4 (leaf node)
  Traverse right: 5 (leaf node)
  Visit root: +
  In postorder, this subtree evaluates as: 4 5 +
• Step 2: Traverse the right subtree rooted at -
Traverse left: 7 (leaf node)
  Traverse right: 2 (leaf node)
  Visit root: -
In postorder, this subtree evaluates as: 7 2 -.
• Step 3: Visit root of the entire tree (*)
  The final postorder traversal of the entire tree is: 4 5 + 7 2 - *

Evaluation Using Postorder Traversal

The traversal sequence tells us how to evaluate the expression in Reverse Polish Notation (RPN), where we evaluate subexpressions from left to right, applying operators after visiting operands.
Postorder Expression: 4 5 + 7 2 - *

1. 4 5 +: Evaluate 4 + 5 to get 9
2. 7 2 -: Evaluate 7 - 2 to get 5
3. 9 5 *: Multiply 9 and 5 to get 45

Cheers! 🚀