Building A Binary Search Tree

Trees are used to organized and store data in computer science. They are one of the most fundamental data structures. A binary tree is a tree type data structure that has many nodes. Each node has a value and may have up to two children nodes, one left and one write. A binary tree starts with a single node and that node is called the root. A binary search tree is a little more special. A binary search tree or a BST sorts the nodes in it a particular way. The values are sorted so that the value of the left child of a parent node is less than the value of a parent node. The value of the right child needs to be greater than the right value of the parent node as well.

With the conditions mentioned above, let’s create a binary search tree. The first things we need to create are the nodes in the tree.

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

As per the above, nodes are created with at least a value. The Node class has three properties, value, left, and right.

With the node created above, we can construct a binary search tree. A BST needs to have a root and we will need to at least have the root as a property of a BST.

constructor(){
    this.root=null
}

To grow our tree, we need to add more nodes to it. The two rules that we want to implement with our tree is for the left node value to be less than the parent node and for the right node value to be greater than the parent node. Those two stipulations are what we need to take in consideration when we add values to our binary tree.

add(value){
        var newNode = new Node(value)
        if(this.root===null){
            this.root=newNode
            return this
        }
}

As per the above code snippet, every time we add to our binary tree, we need to take in a value and create a node to store the value. After the node is created. We check to see if the root is null and if it is, we are assigning the newly created node as the root of the tree.

If the root is not null, we will need a process to evaluate the node value that is being added and compare it to the node that we are at. If the node is greater than the current node value, we will move to the current node’s right child and if it is less, we will need to move to the current node’s left child. If the direction we are moving to has a null value, we can assign the new node as that particular directional node. If the direction that we are moving to has a value, then we assign it as the current node and start our process all over again. With the pseudo code above, the code below should produce a BST with the stipulations that were mentioned at the beginning of this blog.

class BinarySearchTree{
    constructor(){
        this.root=null
    }
add(value){
        var newNode = new Node(value)
        if(this.root===null){
            this.root=newNode
            return this
        }
        
        var current = this.root
        while(true){
            if(value===current.value)return undefined
            if(value<current.value){
                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
            }
        }
    }
}

With the code above, we can add values and build a robust binary tree!

Proost!!!

Kind Regards,

James Wu