Binary Tree - Javascript
by Sanju[ Edit ] 2012-08-28 10:59:31
Binary Tree - Javascript
A binary tree represents data in a tree of nodes. Each node has a value and two children (left and right). In C, this data structure is usually implemented using structures and pointers. This implementation is possible to do in JavaScript using objects and references; however, for smaller trees, there is an easier and quicker way using only one array. The first item of the array will be the head of the tree. Indexes of left and right child nodes if node i can be calculated using the following formula:
leftChild(i) = 2i + 1
rightChild(i) = 2i + 2
As you see, this method isn't exclusive to JavaScript, but it can be very useful when dealing with small trees. You can, for example, write your own helper functions for getting and setting a node's value or children, and traversing the tree, and those methods will be as simple as doing arithmetic calculations and/or for loops. On the other hand, the disadvantage of this method is that wasted space grows as the depth of the tree increases.
