Page 1 of 3 Binary trees in JavaScript? Easy with the right storage mapping function. Find out how to code a binary tree right up to a depth first traversal.
This is one of a series of articles on implementing data structures in JavaScript.
See also:
The binary tree is one of the more useful of the "advanced" data structures and it is fairly easy to implement in JavaScript. However the usual method is to use object references and this makes searching the tree an expensive task. For trees with fixed branching factors e.g. a binary tree with two child nodes attached to every parent node or a ternary tree with three child nodes and so on... there is a very simple but often overlooked way of doing the job.
Instead of using references to link the tree together you can use a storage mapping function to store the data at fixed location. You can think of it as an example of a perfect hash function if you want to but it is simpler to think in terms of storage mapping functions.
The Binary Tree SMF
A binary tree is a tree structure such that each node, apart from the final or terminal nodes, has exactly two children  hence the binary in binary tree.
Each node is associated with a value that takes n bytes to store then a suitable SMF is:
location = base + n*i + n*(2^j1)
which gives the location of the value stored at ith node at the jth level and ^ is the raise to a power operator.
To see why this works consider the following small binary tree:
j node i level 0 0 / \ / \ / \ level 1 0 1 / \ / \ / \ / \ level 2 0 1 2 3
and so on.
Notice that going from one level to the next doubles the number of nodes and you should be able to work out that the number of nodes at level j is simply 2^j.
With this insight you should now also be able to see how the SMF works. The tree is stored as lines of nodes one level at a time. That is:
location 0 1 2 3 4 5 6 node 0  0 1  0 1 2 3 level 0  1  2
To make use of this SMF in a highlevel language all you have to do is declare an array of elements that will hold the node values and use the SMF with n=1 to determine which element node i at level j is stored in.
You should be able to see that you can create a storage mapping function for any tree with a constant branching factor b. All you have to do is change the 2 to b to give:
location = base + n*i + n*(b^j1)
A JavaScript binary tree
The JavaScript Array object can be used to store any object at an indexed location so using this as the basic for out binary tree is an obvious choice.
The first thing we need is the storage mapping function and here we hit our first minor problem. JavaScript doesn't have a "raise to a power" operator. Instead it has the pow method of the Math object. For example,
Math.pow(2,k):
raises 2 to the kth power.
This is what we would have to use for a general tree with a b way branch at each node but for a binary tree we can take a slightly different and theoretically more efficient route.
The shift operators >> and << are equivalent to divide by 2 and multiply by 2 respectively. So
1<<k;
gives the result 2^k.
Using this the storage mapping function:
location = node + 2^level  1
is easy enough to translate into JavaScript. Taking an object oriented approach let's package everything into a BinaryTree object and its associated constructor function:
function BinaryTree(){ this.btSMF=function(level,node){ return node+(1<<level)1; } }
From this point on everything will be defined within the BinaryTree constructor function  a complete listing can be found at the end if you get confused ab about what goes where.
The btSMF function takes a node and level number and returns the location within a standard Array that the node should be stored. We need to declare the array but JavaScript arrays are so good natured we don't have to specify its size  it will grow as needed.
this.Nodes =new Array();
Next we need a basic set and get functions for a node.
this.setNode=function(value,level,node){ this.Nodes[this.btSMF(level,node)]=value; }
this.getNode=function(level,node){ return this.Nodes[this.btSMF(level,node)]; }
These two functions simply store and retrieve the data at the location indicated by the storage mapping function.
To try them out let's store a simple three level tree as shown in the diagram above:
tree=new BinaryTree(); tree.setNode(1,0,0); tree.setNode(2,1,0); tree.setNode(3,1,1); tree.setNode(4,2,0); tree.setNode(5,2,1); tree.setNode(6,2,2); tree.setNode(7,2,3);
and to retrieve a value you would use something like:
alert(tree.getNode(2,1));
<ASIN:0137054890> <ASIN:0596517742> <ASIN:1590597273>
