A Binary Search Tree in Javascript

OCTOBER 18, 2013

Why Am I Creating a Binary Search Tree?

I am a pretty practical developer. I usually only learn what I need to know to get the job done. Lately that means fairly straightforward ways of organizing functionality. I often find myself doubting my own skills. Tomorrow I am doing a hackathon [AngelApp], and I want to do something special. I also want to advance my career into dealing with larger scale application development. Finally, it's interesting to challenge my mind. This wasn't much of a challenge, but it's the first step to proving myself.

The Challenge

Using javascript, underscore, and d3.js, create a binary tree structure, showing the structure visually.

Starting Out

I am starting by reading. TopCoder has a nice article. I know a little about search algorithms, but I am not using what I know, so I am using this article as a refresher. I started by reading through the TopCoder article, and building a tree in my imagination. I quickly ran into a memory issue when I started getting into removing a node. Adding a node was easy. So, I started writing code for adding a node.

var svgContainer = d3.select("body").append("svg")
    .attr("width", 1000)
    .attr("height", 1000);

function drawCircle(x, y, value) {
    console.log(x, y, value);
    var circle = svgContainer.append("circle")
        .attr("cx", x)
        .attr("cy", y)
        .attr("r", 10)
        .attr('fill', 'black')
        .style("stroke", "grey")
        .style("stroke-width", 1);
    var text = svgContainer.append("svg:text")
        .attr("x", x)
        .attr("y", y)
        .attr("dx", 0)
        .attr("dy", 5)
        .attr('fill', 'white')
        .attr("text-anchor", "middle")
        .text(value);
    return circle;
}

var tree = {
    root: null,
    addToTree: function (value) {
        if (_.isEmpty(this.root)) {
            this.root = new node(value);
        } else {
            this.root.addNode(value);
        }
    }
};
var node = function (val, par, side) {
    this.x = 250;
    this.y = 50;
    if (!_.isUndefined(par)) {
        var offset = Math.random() * 40;
        this.y = par.y + 40;
        this.x = par.x + (side * (20 + offset));
        var myLine = svgContainer.append("svg:line")
            .attr("x1", par.x)
            .attr("y1", par.y + 8)
            .attr("x2", this.x)
            .attr("y2", this.y - 8)
            .style("stroke", "black")
            .style("stroke-width", "5");
    }
    this.$node = drawCircle(this.x, this.y, val);
    this.left = null;
    this.right = null;
    this.parent = par,
    this.value = val;
    this.addNode = function (value) {
        if (value < this.value) {
            if (_.isNull(this.left)) {
                this.left = new node(value, this, -1);
            }
            this.left.addNode(value);
        }
        if (value > this.value) {
            if (_.isNull(this.right)) {
                this.right = new node(value, this, 1);
            }
            this.right.addNode(value);
        }
    };
};

var nums = _.shuffle(_.range(20));
while (nums.length) {
    var num = nums.pop()
    tree.addToTree(num);
}

Here is a jsFiddle showing it functioning. This code example is generating a random ordering of the numbers 0-100, and adding them to a binary search tree.

Step Two - Going the Extra Mile (Removing a Node)

The rules for removing a node from a BST are (from TopCoder):

Deleting a node from BST is a little more subtle. Formally there are three cases for deleting node n from a BST:
If n has no children, we only have to remove n from the tree.
If n has a single child, we remove n and connect its parent to its child.
If n has two children, we need to :
Find the smallest node that is larger than n, call it m.
Remove m from the tree (if you have reached this case then m will always have no left child, though I'll leave the proof to the reader), so we apply one or the other of the above cases to do this.
Replace the value of n with m.
Removing a node that has no children is easy, just traverse to the parent, find this node, and replace it with null. Javascript's garbage collection should do the rest.

Removing a node with a single child is easy too, just traverse to the parent, find this node, and replace it with this node's only child.

Spotting a Congruence and Using One Code Path

Several removal paths require the same functionality. Nodes need to traverse to their respective parent, and find and replace a reference to themselves from the parent. Writing the method below meets that necessity in a unified way.

Checking (this.parent.left == this), should indicate if the parent's left node is this node. Otherwise, the right node is this.

The method takes one argument: the node or null, with which replaces the current node. It will need to be able to go to it's parent and then find itself, and replace itself.

this.reassignThis = function (node) {
    if (this.parent.left == this) {
        this.parent.left = node;
    } else {
        this.parent.right = node;
    }
};

Removing a node, when it has children, requires some extra magic. I need three functionalities:

  • traverse the tree from the top in search of the next largest number
  • remove m (using the same function we build here)
  • replace the value of this node with the value of the node found in step 1

NOTE: the #3 states replace: the value, not the node.

Jumping In - Coding Starts, and an Untested Solution Emerges

Node deletion is tricky because of possibility 3 (if node has two children). At that point I naturally started adding more methods... to be continued...