Complete Binary Tree Code Implementation in JavaScript

Use Case:

Binary tree data structures consist of nodes who contain some data, point to a parent node and have up to 2 children. Each node is greater than the its child on the left and smaller than its child on the right.

A few reasons why binary trees might be used in place of other data structures including arrays, stacks or queues include:

  • Trees may best represent the hierarchy of the data set with their parent/child relationships
  • Binary trees are very efficient at core functions such as inserting new values and searching - O(log n) or logarithmic time for both
  • Trees are flexible data structures allowing for reorganization of parents and children

Below is a complete implementation of a binary tree in JavaScript including functionality for finding nodes, inserting nodes, returning a range of nodes, deleting nodes, keeping track of the size, height and depth of nodes, and keeping the trees balanced and AVL compliant for efficiency purposes.

Here is what each node will look like:

And here is what we will have built by the end of this exercise:

1. Node Class

JavaScript

function Node(key) {
	this.key = key
	this.parent = null
	this.height = 1
	this.size = 1
	this.depth = 0
	this.left = null
	this.right = null
}

The first thing that we need to do is set up our Node class that will accept the parameter key and set it's key equal to that parameter. Each node will hold the following information:

  • Key: What we'll use as the value for each node in this example
  • Parent: The parent that the node belongs to
  • Height: The height of the current node. Each node has a height of at least 1 plus the height of it's tallest child.
  • Size: The number of nodes that are children/grandchildren of the current node. Each node will have a size of at least 1 plus the size of it's children combined.
  • Depth: How far removed the node is from the tree's root.
  • Left: The left child of the node.
  • Right: The right child of the node.

2. Tree Class

JavaScript

function Tree(key) {
var node = new Node(key)
	this.root = node
}

Next, we'll create our Tree class. Since a tree is just a data structure containing nodes, the only variable we need to keep track of is the tree's root. We'll also accept key as a paramater and use that to create the first node in our tree.

3. Find Function

JavaScript

Tree.prototype.find = function(k, R) {
	if (R.key == k) { // If equal to root key
		return R
	} else if (k < R.key) { // If less than root key
		if (R.left) { // If left child is not null
			return this.find(k, R.left)
		}
		return R // If no left child, return place
	} else if (k > R.key) { // If greater than root key
		if (R.right) { // If right child is not null
			return this.find(k, R.right)
		}
		return R // If no right child, return place
	}
}

Our first function belonging to our tree will be our find function that we'll use to traverse through our tree to find a specific node. This function will accept k - the value of our node (in this tree, the value will always be a node's key), and R -the root of our tree.

If the key is the root's key, then we'll return the root as being found. If the key is less than the root's key and it has a left child, we'll continue our search in the node's left child. If the left child doesn't exist we'll return the current node which we'll use as the placeholder for where our next node should go.

If the key is greater than the root's key and the root has a right child, we'll continue our search in the node's right child. If the right child doesn't exist we'll return the current node as a placeholder.

4. Range Search Function

JavaScript

Tree.prototype.rangeSearch = function(x,y) {
	var L = [] // Array to store our results
	var N = this.find(x, this.root) // Turn x into node
	while (N.key <= y) { // If new node's key is less than or equal to y
		if (N.key >= x) { // If new node's key is greater than or equal to x
			L.push(N) // Add to array
		}
		N = this.next(N) // Continue in range
	}
	return L // Return array of results
}

Now we want the ability to find and return a range of nodes. We can do this by creating a functioned called rangeSearch that will accept 2 values, x and y to search between. First, we'll create an empty array of L to hold our array of results. Then, we'll use our find function that we just declared to return the first found node in our range. Then we'll check to see if it's key is less than or equal to y - the top of our range. While it is, if it's greater than or equal to the bottom of our range we'll push it to our results array.

Then we'll return our results array of L.

You'll notice we called a new function inside of rangeSearch. Let's declare that below.

5. Next Function

JavaScript

Tree.prototype.next = function(N) {
	if (!N.key) {
		var N = this.find(N, this.root)
	}
	if (N.right) {
		return this.leftDescendant(N.right) // If right child exists, get descendant
	} else {
		return this.rightAncestor(N) // Else get ancestor
	}
}

The next function will be used to find the next node in our tree when given a node - which we'll do by giving the function an initial paramater of N. If N isn't a node already, use the find function to set it as a node.

If the node has a right child, find the left descendant of that child. Else, find the right ancestor of the current node.

We called 2 new functions. Let's break them down.

6. Left Descendant Function

JavaScript

Tree.prototype.leftDescendant = function(N) {
	if (!N.left) { // If no left child, return
		return N
	} else {
		return this.leftDescendant(N.left) // Else find descendant of left child
	}
}

With our leftDescendant function, we'll see if the node has a left child. If it doesn't we'll just return the current node. If it does, we'll recurse the function on the node's left child.

7. Right Ancestor Function

JavaScript

Tree.prototype.rightAncestor = function(N) {
	if (N.parent) { // If parent is not null
		if (N.key < N.parent.key) { // If node's key is less than parent's key
			return N.parent // Return parent
		} else {
			return this.rightAncestor(N.parent) // Else find ancestor of parent
		}
	}
}

The rightAncestor function will be used to find the next node based on the current node's parent. If the current node has a parent, we'll check to see if the current node's key is less than its parent's key. If it is, we'll return the parent. If it isn't, we'll recurse the function on the parent node.

8. Insert Function

JavaScript

Tree.prototype.insert = function(k) {
	P = this.find(k,this.root) // Get place to insert node
	var node = new Node(k) // Create new node
	node.parent = P // Set parent
	node.parent.size++ // Increment size of parent
	if (P && k > P.key) { // If new value is greater than place
		P.right = node // Set parent's right child to new node
	} else {
		P.left = node // Set parent's left child to new node
	}
	return node // Return new node
}

Now we need to way to inset new nodes into our tree, so we'll create a new insert function. This function will accept a parameter k which will hold the value (key) of our new node. Then, we'll call the find function to locate the place where our new node should be located. Once we've determined that, we'll create the new node based on the value submitted, set the node's parent to P - the place, increase the size of the parent to account for the added node, and then, whether the new node is bigger or less than the value of the parent, we'll add it as a child node of the parent. Finally, we'll return the new node.

This function inserts a new node into our tree, but it doesn't keep the tree balanced when doing so. In fact, if we use this function as-is to insert a bunch of nodes, we could end up with something like this:

This won't work for our binary tree implementation because, for efficiency purposes, we want the sizes of the root nodes children to be the same (or within 1). So we're going to add a new function upon insertion that will keep our tree balanced.

9. AVL Insert Function

JavaScript

Tree.prototype.avlInsert = function(k) {
	var N = this.insert(k, this.root) // Set N equal to insertion of new node
	this.adjustDepth(N) // Adjust depth of the new node
	this.rebalance(N) // Rebalance tree based on node size
}

Our new avlInsert function will insert new nodes via the previous insert function we just created, but afterward it will do 2 things - adjust the depth of the new node and then rebalance it.

10. Rebalance Function

JavaScript

Tree.prototype.rebalance = function(N) {
	if (N.parent) { // If node has parent, set equal to P
		var P = N.parent
	}
	if (N.left && N.right) { // If node has both a left and right
		if (N.left.size > N.right.size + 1) { // If left size is greater than right size plus 1
			this.rebalanceRight(N) // Rebalance on the right side
		}
		if (N.right.size > N.left.size + 1) { // If right size is greater than left size plus 1
			this.rebalanceLeft(N) // Rebalance on the left side
		}
	} else if (N.left && N.left.size > 1) { // If no right child but left size is greater than 1
		this.rebalanceRight(N) // Rebalance on the right side
	} else if (N.right && N.right.size > 1) { // If no left child but right size is greater than 1
		this.rebalanceLeft(N) // Rebalance on the left side
	}
	this.adjustHeight(N) // Update heights
	this.adjustDepth(N) // Update depths
	if (P) { // If node had parent, recurse rebalance function with parent
		this.rebalance(P)
	}
}

The main purpose of our rebalance function is to determine where the tree is unbalanced by looking at node sizes and then calling a few new functions to rebalance the tree post the addition of the new node.

If the node's left child's size is greater than it's right child's size plus 1 then it's unbalanced, and we need to call the rebalanceRight function. If the node doesn't have a right child and the size of it's left child is greater than 1, then we'll call the same function.

If the opposites are true, then we'll call the rebalanceLeft function.

After we balance the children, we'll readjust the height and depth of the node to account for the changes, then recurse up to check the balance of the node's parent.

11. Rebalance Right and Rebalance Left Functions

JavaScript

Tree.prototype.rebalanceRight = function(N) {
	var M = N.left // Set M equal to node's left child
	if (M.right && M.left && M.right.size > M.left.size) { // If M has both right and left children and M's right size is greater than it's left size
		this.rotateLeft(M) // Rotate left on M
	} else if (M.right && M.right.size > 1) { // If M has a right child and it's size is more than 1
		this.rotateLeft(M) // Rotate left on M
	}
	this.rotateRight(N) // Rotate right on N
}

Tree.prototype.rebalanceLeft = function(N) {
	var M = N.right // Set M equal to node's right child
	if (M.right && M.left && M.left.size > M.right.size) { // If M has both right and left children and M's left size is greater than M's right size
		this.rotateRight(M) // Rotate right on M
	} else if (M.left && M.left.size > 1) { // If M has a left child and it's size is more than 1
		this.rotateRight(M) // Rotate right on M
	}
	this.rotateLeft(N) // Rotate left on N
}

We'll call the rebalanceRight and rebalanceLeft functions together since they're mirror-images of eachother, and we'll walk through the first one.

In the rebalanceRight function, we'll set the variable M equal to the node's left child. Then we'll check to see if M has a right and left child and if the right child's size is bigger than the left child's. If so, or if M doesn't have a left child and the size of it's right child is bigger than 1, we'll rotate the node to the left. Then, we'll rotate the original node -N - to the right.

12. Rotate Right and Rotate Left Functions

JavaScript

Tree.prototype.rotateRight = function(X) {
	var P = X.parent // P is parent of current node
	var Y = X.left // Y is current node's left child
	var B = Y.right // B is Y's right child
	Y.parent = P // Set Y's parent equal to X's parent
	if (Y && P) { // If Y and P not null
		if(Y.key > P.key) { // If Y bigger than P - X's parent
			P.right = Y // X's parent's right child equal to Y
		} else {
			P.left = Y // X's parent's left child equal to Y
		}
	}
	if (X.parent == null) { // If X is current root node
		this.root = Y // Set Y as the tree's new root
	}
	X.parent = Y // Set X's new parent to Y
	X.left = B // Set's X's left child to B
	Y.right = X // Set Y's right child to X
	if (B) { // If Y has a right child
		B.parent = X // Set it's parent to X
	}
	this.recomputeSize(X) // Recompute size of X
	this.recomputeSize(Y) // Recompute size of Y
	if (P) { // If P or X's parent is not null
		this.recomputeSize(P) // Recompute size of P
	}
}

Tree.prototype.rotateLeft = function(X) {
	var P = X.parent // P is parent of current node
	var Y = X.right // Y is current node's right child
	var B = Y.left // 8 is Y's left child
	Y.parent = P // Set Y's parent equal to P - X's parent
	if (Y && P) { // If Y and P not null
		if (Y.key > P.key) { // If Y greater than P
			P.right = Y // Set X's parent's right child equal to Y
		} else {
			P.left = Y // Set X's parent's left child equal to Y
		}
	}
	if (X.parent == null) { // If X is current root node
		this.root = Y // Set Y as the tree's new root
	}
	X.parent = Y // Set X's new parent as Y
	Y.left = X // Set Y's left child as X
	if (B) { // If Y has a left child
		B.parent = X // Set Y's left child equal to X
	}
	X.right = B // Set X's right child equal to B - Y's former left child
	this.recomputeSize(X) // Recompute size of X
	this.recomputeSize(Y) // Recompute size of Y
	if (P) { // If P or X's parent is not null
		this.recomputeSize(P) // Recompute size of P
	}
}

We'll also call the rotateRight and rotateLeft functions together since they are mirror-images of each other. Let's go through the rotateRight function together.

It looks like a lot here, but really we're just reassigning parent and child nodes. We're going to set P equal to the parent of X , Y equal to X's left child, and B equal to Y's right child. Then Y's parent is now going to be P and if Y is bigger than P it'll be it's right child - otherwise, it's left child.

If X's parent is null then that means it's currently the tree's root node. We're going to change that and set the root of the tree equal to Y. X's new parent is now Y and it's left child has been changed from Y to B. Meanwhile, Y's right child has been changed to X. If B is not null, then it's parent is set to X.

Now that we've reassigned the nodes, we need to call the recomputeSize function on the affected nodes - X, Y and, if it exists, P.

The rotateLeft function is the same but opposite - refer to the many comments added in the code for help and organization purposes!

13. Recompute Size Function

JavaScript

Tree.prototype.recomputeSize = function(N) {
	var size = 1 // Start with size of 1
	if (N.left) { // If node has left child
		size += N.left.size // Add size of left child
	}
	if (N.right) { // If node has right child
		size += N.right.size // Add size of right child
	}
	N.size = size // Set node's size equal to size variable
}

As called in the rotate functions, recomputeSize takes a node and recomputes its size based on its children nodes plus 1 (to include itself).

14. Adjust Height Function

JavaScript

Tree.prototype.adjustHeight = function(N) {
	if (N.left && N.right) { // If both left and right children
		N.height = 1 + Math.max(N.left.height, N.right.height) // New height is 1 plus the max between the left and right heights
	} else if (N.left) { // If not both, but left child exists
		N.height = 1 + N.left.height // New height is 1 plus height of left child
	} else if (N.right) { // If not both but right child exists
		N.height = 1 + N.right.height // New height is 1 plus height of right child
	} else {
		N.height = 1 // If no children, new height is 1
	}
	if (N.parent) { // Recurse adjustHeight on parent till root node
		this.adjustHeight(N.parent)
	}
}

In addition to the previous function that recomputes the size of the node, we also need to cover the adjustHeight and adjustDepth functions that were first called in the rebalance function.

This function updates the height of the node based on the heights of its children. A node's height is the height of its tallest child plus 1 (to include itself). We'll just JavaScript's native Math.max function to determine which child is taller if they both exist.

15. Adjust Depth Function

JavaScript

Tree.prototype.adjustDepth = function(N) {
	if (N.key < this.root.key) { // If this node is on the left side of the tree
		N.depth = this.root.left.height - N.height + 1 // New depth is height of root's left child - height of current node plus 1
	} else if (N.key > this.root.key) { // If this node is on right side of tree
		N.depth = this.root.right.height - N.height + 1 // New depth is height of root's right child - height of current node plus 1
	} else if (N.key == this.root.key) { // If node is root
		N.depth = 0 // New depth is 0
	}
	if (N.right) { // If node has right child, recurse adjustDepth function
		this.adjustDepth(N.right)
	}
	if (N.left) { // If node has left child, recurse adjustDepth function
		this.adjustDepth(N.left)
	}
}

Our adjustDepth function will calculate the depth of the given node. The depth is the node's distance away from the root of the tree. So, to calculate this, we'll use the height of the root node's left or right child (depending on what side of the tree the current node exists on) and subtract the current node's height from it and add 1 to get our depth. Then we'll recurse to the node's children to update them as well.

16. Delete Function

JavaScript

Tree.prototype.delete = function(N) {
	if (!N.key) {
		var N = this.find(N, this.root) // Set N equal to node of key N
	}
	if (N.right) { // If node has a right child
		if (N.right.key > N.parent.key) { // If node's right key is greater than node's parent key
			N.parent.right = N.right // Set parent's right equal to replacing node
		} else {
			N.parent.left = N.right // Else set parent's left equal to replacing node
		}
		N.right.parent = N.parent // Set the parent of the replacing node
		N.right.depth-- // Reduce it's depth by 1
	} else if (N.left) { // Else if node has left child
		if (N.left.key > N.parent.key) { // If node's left key is greater than node's parent key
			N.parent.right = N.left // Set parent's right equal to replacing node
		} else {
			N.parent.left = N.left // Else set parent's left equal to replacing node
		}
		N.left.parent = N.parent // Set the parent of the replacing node
		N.left.depth-- // Reduce it's depth by 1
	}
	var temp = N // Set temp equal to node to be deleted
	delete N // Delete node
	return temp // Return deleted node
}

We may also need to delete a node at times so let's add a function to do that.

The delete function isn't as simple as just removing a node because it could potentially break our tree if the node has child nodes. So we need to delete the node and declare a node to take it's place. If the node has a right child, we'll start there and compare it to the original node's parent. If not, we'll try the left node. Then we'll set the original node equal to the temp variable before deleting so that we can return the deleted node.

But this could still potentially mess up our tree - or at least the balance of it. So we need to add a way for nodes to be deleted while maintaining balance.

17. AVL Delete Function

JavaScript

Tree.prototype.avlDelete = function(N) {
	var N = this.find(N, this.root) // Create node from inserted value
	var M = N.parent // Set M equal to node's parent
	this.delete(N) // Delete node using delete function
	this.rebalance(M) // Rebalance tree with M
}

In our avlDelete function, we'll find the node containing the submitted key, and then we'll find it's parent. Then we'll call the delete function on the node and the rebalance function on it's parent - M.

18. Order Statistic Tree Function

JavaScript

Tree.prototype.orderStatistic = function(R, k) { in the tree
	if (R.left) { // If root node has left child
		var s = R.left.size // Set s equal to size of left child
	} else {
		var s = 0 // Set s equal to 0
	}
	if (!k.key) { // If not node, set k equal to its node
		var k = this.find(k, R)
	}
	if (k.size == s + 1) { // If k's size is equal to s + 1
		return R // Return the root node
	} else if (k.size < s + 1) { // If k is less, recurse the function with the root's left size
		return this.orderStatistic(R.left, k)
	} else if (k.size > s + 1) { // If k is greater, recurse the function with the root's right side
		return this.orderStatistic(R.right, k.size - s - 1)
	}
}

With our orderStatistic function we can return the kth smallest element (and determine the rank of a node) in our tree (kth referring to the value for k that we're submitting). This allows us to emulate the functionality of an Order Statistic Tree in our binary tree in O(log n) time.

Here, we'll recurse the function looking for the node with the matching size of k starting with the tree's root.

19. Range Sum Function

JavaScript

Tree.prototype.rangeSum = function(x,y) {
	var range = this.rangeSearch(x,y) // Get array of nodes in range
	var sum = 0 // Set sum equal to 0
	for (i = 0; i < range.length; i++) { // Loop through nodes in range
		sum += range[i].key // Increase sum per keys
	}
	return sum // Return result
}

Finally, we'll call a simple rangeSum function to, in this scenario, leverage the previously declared rangeSearch function to return an array of nodes that fall within the given range, and then iterate through the results and sum up the key values.

This would be a simple way to sum or concatenate values in a range regardless of data type - integer, string, or other.

Create the Tree

JavaScript

var tree = new Tree(5)
tree.avlInsert(4)
tree.avlInsert(2)
tree.avlInsert(3)
tree.avlInsert(7)
tree.avlInsert(1)
tree.avlInsert(6)
tree.avlInsert(9)
tree.avlInsert(8)
tree.avlInsert(10)
tree.avlInsert(11)
tree.avlInsert(14)
tree.avlInsert(12)

Finally, we can create our tree, insert into it, delete from it, find nodes in it, and many of the other functions we mentioned above. After inserting the above nodes, our tree should be organized like how it is in the picture at the beginning of our post.

Tweet me @tylerewillis

Or send me an email: