Storing Data Elements

We want to index our eight presidents by their first name + last name, as well as their last name + first name. Adhering to the principles of the trie, here is how we build the trie for the eight presidents. First we allocate memory for the top level 10-element array, called tree:

var tree = new Array(10);

Then we allocate memory for another 10-element array:

var tmpArray = new Array(10);

which we assign tree[2] to point to:

tree[2] = tmpArray;

Now we have a 10-element array at the second element of the top level tree array. The phone key number 2 is associated with the letters A, B, and C. From our eight presidents, the following ones start with either A, B, or C (first name or last name): Carter, Bill (Clinton), Clinton, and Bush. Since we don't have any collision between their second letter, we can store them at the current level of hierarchy:

tree[2][2] = 2; // Carter, Jimmy
tree[2][4] = 4; // Bill Clinton
tree[2][5] = 4;  // Clinton, Bill
tree[2][8] = 6; // Bush, George

Let's examine what's happening at the digit 3. The key 3 is associated with the letters D, E, and F. Quick scanning of the president list, we find that only Ford is indexed by the digit 3. Hence, we can store him at the top level tree array, element number 3:

tree[3] = 5; // Ford, Gerald

The digit 4 (associated with G, H, and I) is more crowded. First we create two more levels of hierarchies, one at tree[4] and one at tree[4][3]:

var tmpArray = new Array(10);
tree[4] = tmpArray;
var tmpArray = new Array(10);
tree[4][3] = tmpArray;

Two names crowd the digit 4:

tree[4][3][7] = 5; // Gerald Ford
tree[4][3][6] = 6; // George Bush

The digit 5 is associated with J, K, and L, and is loaded with five names. The first three are Jimmy Carter, Lyndon Johnson, and Kennedy (John). Allocating one array at tree[5] is sufficient:

var tmpArray = new Array(10);
tree[5] = tmpArray;
tree[5][4] = 2; // Jimmy Carter
tree[5][9] = 7; // Lyndon Johnson
tree[5][3] = 8; // Kennedy, John

The interesting pair is John Kennedy and Johnson (Lyndon). As you can see you need five level or hierarchies before you can distinguish between them:

var tmpArray = new Array(10);
tree[5][6] = tmpArray; 
var tmpArray = new Array(10);
tree[5][6][4] = tmpArray;
var tmpArray = new Array(10);
tree[5][6][4][6] = tmpArray;
tree[5][6][4][6][5] = 8; // John Kennedy
tree[5][6][4][6][7] = 7; // Johnson, Lyndon

Nixon (Richard) is alone on digit 6, associated with M, N, and O:

tree[6] = 3; // Nixon, Richard

Finally, we need one level of hierarchy at digit 7, associated with P, R, and S, for Reagan (Ronald), Richard Nixon, and Ronald Reagan:

var tmpArray = new Array(10);
tree[7] = tmpArray;
tree[7][3] = 1; // Reagan, Ronald
tree[7][4] = 3; // Richard Nixon
tree[7][6] = 1; // Ronald Reagan