Hi,

I need to store each path in a tree as a row in a two dimensional array of size #of paths x N. I couldn't find the appropriate indexing scheme for the array. Any ideas would be appreciated. Thanks,

Sorry for the typing mistake in the title :)
Correct title: "Representing a tree as a two dimensional array"

I need to store each path in a tree as a row in a two dimensional array of size #of paths x N. I couldn't find the appropriate indexing scheme for the array.

Could you clarify your question? Is it a binary tree or an n-ary tree? What do you mean by 'each path in a tree'? Or is it a directed acyclic graph?

it is not a binary tree.. each parent could has the same number of children but not necessarily 2 children. Each path means the set of nodes from the root to a leaf.. so each row in the array should contain the set of nodes from the root to one leaf

Let us say that we have a full 3-ary tree as follows:

[B]root[/B] 0
                                           |
                  -------------------------------------------------
                  |                        |                      |
                [B]alpha[/B] 1                   [B]beta[/B] 2                 [B]gamma[/B] 3
                  |                        |                      |
        --------------------     --------------------     --------------------
        |         |        |     |         |        |     |         |         |
      [B]delta[/B] 4  [B]epsilon[/B] 5  [B]zeta[/B]   [B]eta[/B]      [B]theta[/B]    [B]iota[/B]  [B]kappa[/B]    [B]lambda[/B]      [B]mu[/B]
        |
--------------------
|        |         |
[B]nu[/B]       [B]xi[/B]      [B]omicron[/B]

A two dimensional array representation of this tree (in the manner required) could be:

row 0: root, alpha, delta, nu
row 1: root, alpha, delta, xi
row 2: root, alpha, delta, omicron
row 3: root, alpha, epsilon, null
row 4: root, alpha, zeta, null
row 5: root, beta, eta, null
row 6: root, beta, theta, null
row 7: root, beta, iota, null
row 8: root, gamma, kappa, null
row 9: root, gamma, lambda, null
row 10: root, gamma, mu, null


If the full tree is a complete tree (every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible), a one dimensional array representation is possible. For the complete 3-ary tree above:

root, alpha, beta, gamma, delta, epsilon, zeta, eta, theta, iota, kappa, lambda, mu, nu, xi, omicron
  0     1     2      3      4       5       6    7     8      9     10     11    12  13  14    15

The position of the children of node at position p would be p*3+1, p*3+2, p*3+3
The position of the parent of node at position c would be (c-1)/3

In general, for a complete n-ary tree,
The position of the children of node at position p would be p*n+1, p*n+2, .. p*n+n
The position of the parent of node at position c would be (c-1)/n

Comments
NIce greek letter skills
Excellent post, as always.
Nice diagram.

Yes it is a complete n-ary tree. How I can traverse all the paths?. Thanks,

Compute the depth D of the n-ary tree.
The two dimensional matrix representation will have D columns.

Perform a traversal (say a postorder traversal) of the n-ary tree. During the traversal,

a. Push each node encountered onto a stack. (the first node pushed would be the root).

b. If the node is a leaf node:
        Add the entire contents of the stack as a row of the 2D array. 
        If the size of the stack is less than [b]D[/b], add a [b]null[/b] at the end. 
        (with a complete n-ary tree, more than one [b]null[/b] will never be required.)

    Else:
        Move down to the next level, processing each of the [b]n[/b] children one by one.

c. Pop the node just visited off the stack, move up one level and continue with the traversal.
This article has been dead for over six months. Start a new discussion instead.