Creating a Binary Search Tree, inserting and LeetCode 653

Binary Search Trees are pretty cool! Their time complexity is o (log n) at their average time complexity. Their worst case time complexity is o (n).

Space complexity wise, it is dependent on how many nodes we continue to insert. This means the space complexity is o (n).

Please note, that this article is in Javascript.

How to create a BST:

To create a BST, you need to initialize a class of BST and a class of Node. First, we should talk about creating a node class:

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

The constructor allows us to create a node object instance of a class. Here, we are saying that given a value, we can set either of the three variables to equal the new value.

Now, lets create the BST class:

class BST {
    constructor (val) {
     this.root = null 
   }
}

Here, we initialized a variable, this.root, to be equal to null. This variable represents the genesis of the tree.

Now, that we have created our node and BST classes, let’s go ahead and create the insert function. This function will reside inside of the BST class

class BST {
    constructor (val) {
      this.root = null 
   }
   insert (val) {
      
   }
}

How to insert into a BST

First, we create the function.

Here is the pseudocode for the insert:

1. Create a variable newNode that takes in a new Node from the previous class.
2. If there is no root, then given the value of new node, assign the new node to be the root.
3. Create a variable called current to be equal to the root.
4. While true, if the current value is equal to the value given in the parameter, return undefined.
5. If the value is less than the current value, and if the current.left is null, assign the current.left equal to newNode. Once this is assigned, reassign current to be current.left (aka null)
6. If the value is greater than the current value, and if the current.right is null, assign the current.right = to the newNode. Once this is assigned, reassign the current to be current.right (aka null)

class BST {
   constructor() {
   this.root = null
   }
   insert(val){
   let newNode = new Node(val)
   if (!this.root) {
   this.root = newNode
   return this;
  }
   let current = this.root;
   while (true){
   if (current.val === val) return undefined;
     if (val < current.val) {
         if (current.left === null) {
            current.left = newNode
            return this;
         }
      current = current.left
      } else {
         if (current.right === null) {
         current.right = newNode 
         return this;
        }
     current = current.right
     }
   }
}

Now you can call upon the new BST class to create a new Tree.

let newTree = new BST()

And, you can now insert values into it:

newTree.insert(5)
newTree.insert(6)
newTree.insert(7)
newTree.insert(3)

This will look like this:

    5
  /  \
3      6
         \
           7

Now, let’s cover how to find two values in a tree that add up to a target.

To solve leetcode 653, we will be using a hash to store all the differences of the target and the current node value. If the current iteration is in the hash, as a result of finding the difference, then we can return true (some interviewers might ask you to return the two nodes).

I will be using DFS and the iterative approach to solving this problem.

LeetCode 653

const traverseDFS = (tree, k) => {
    let hash = new Set() // o (1)
    let stack = [tree]
    while (stack.length > 0) {   // o (n)
       let current = stack.pop()
       
       if (hash.has(current.val)) {
         return true 
      }  
       hash.add(k - current.val)
       if (current.left) stack.push(current.left) 
       if (current.right) stack.push(current.right)
   }
   return false 
}

At it’s worst, the time and space complexity for this problem will be at o (n).

Please let me know if this helps!

Happy hacking!

-Crystal