Binary Search Tree

A binary search tree is a tree with the following properties

1. Ordered Structure: A search tree must be ordered in the sense that all nodes to the left of the tree must be less than the value of that node and all node to the right of the tree must be greater than the value of that node
2. Tree Structure**: All nodes must point to at most 2 nodes (left node and right node) called children of that node

1.1. Time Complexity
Since a binary search tree has an ordered structure operations on it are very efficient

Take the tree above for example, to find the Node with the value of 7 we don't have to to look at every single node in the tree, since we know every node larger than the current node must be to the right of that node we can use the divide and conquer algorithm to find that node

1. Start at the root.
2. Compare with the current node:
   • If equal, target found.
   • If less, go left.
   • If greater, go right.
3. Repeat recursively in the chosen subtree until the target is found or the subtree is empty.

using this algorithm it would take exactly 3 steps at worse case to find the node with the value of 7 which is an O(logn) operation
Insert, Lookup and Remove have the same complexity of O(logn)

1.2. Node

A node in a binary search tree consist of three things, the value, pointer to the left and a pointer to the right (since each node can have elements to the left and right of itself).
In practice, a node would look like this

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

2.0. Creating a binary search Tree

To create a tree, we need have a pointer to the root node in the tree or it would get garbage collected since it dosen't have an value assigned to it (The root node is the first node in the tree). A binary search tree constructor would look like this

class BinarySearchTree {
  constructor(value){
    const newNode = new Node(value)
    this.root = newNode
  }
}

In the example above we create a root node at the time of creating the Tree, It doesn't have to be doe this way, we can use the insert method to add elements to the tree. In this case the root node would be set to null at the time we are creating the Tree

constructor(){
  this.root = null
}

3.0. Operations on a binary tree

Now we have our search tree class we'll look at the various method on that class

3.1. Insert

To insert a node to a tree we use the following sequence of operations

1. Create a node
2. if root === null then root = node. End
3. Compare node with current item on the tree
   • if less consider the node to the left
   • if greater consider the node to the right
4. if null insert a node there else repeat go to step 3
5. End

  insert(value){
    const newNode = new Node(value)
    if(!this.root){
      this.root = newNode
      return this
    }
    const tempNode = this.root
    while(true){
     if(value == this.root.value) return undefined
     if(value > this.root.value){
       if(this.root.right == null){
        this.root.right = newNode
        return this
       }
       tempNode = this.root.right
     }
     if(value < this.root.value){
       if(this.root.left === null){
        this.root.left = newNode
        return this
       }
       tempNode = this.root.left
     }
    }
}

3.1. Contains

The contains method checks if a value is present in the binary tree. The fun thing about binary tree is that all methods we would see in this article has similar algorithms with a very tiny modification as we would see below
Pseudocode

1. if root === null then return false
2. loop through the tree
3. Compare value with current item on the tree
   • if less consider the node to the left
   • if greater consider the node to the right
   • if element is equal, return true
4. return false
5. End

contains(value){
 if(!this.root) return false
 const temp = this.root
 while(temp){
  if(value === temp.value) return true
  if(value > temp.value){
   temp = temp.right
  }else{
   temp = temp.left
 }
 return false
}

4.0. Conclusion

In conclusion, understanding binary search trees is not just an academic exercise; it's a powerful tool that forms the backbone of many computing applications. As we've seen, the efficient search operations and simple yet elegant structure of BSTs make them indispensable in various fields. Whether you're optimizing database queries or implementing efficient search algorithms, the principles of binary search trees will continue to play a crucial role. As you continue your journey in data structures and algorithms, remember that mastering BSTs is not just about memorizing algorithms; it's about unlocking a deeper understanding of how computers efficiently organize and retrieve information.