I don’t use tree data structures very often. But when I do need a tree (typically a decision tree classifier) , I avoid using a recursion approach and use a List data structure. Recursive data structures are cool and mysterious, but in a production environment simplicity is always better than coolness.

With a List data structure it’s easy to know exactly where any child or parent node is. Suppose you have a tree with seven nodes:

      0
  1       2
3   4   5   6

If each node has an ID i, where root = 0, left child of root = 1, right child of root = 2 and so on then:

The left child of i is located at index [2i + 1]
The right child of i is located at index [2i + 2]

If i is an odd number (i % 2 != 0) the node is a left child.
If i is even the node is a right child

A left child parent is at [(i-1) / 2]
A right child parent is at [(i–2) / 2]

Simple, easy, and efficient.

To traverse a tree implemented as a List, you just walk through the List in order:

for i = 0 to numNodes
  display(tree[i])
end-for

The will display the tree level by level: (0, 1, 2, 3, 4, 5, 6). Traversing level-by-level is perfectly fine for most problem scenarios. But suppose you want to traverse/display the tree in what’s called an inorder manner. This is a common ordering because it’s easy to do for a recursive tree:

display(root)
  if root != null
    display(root->left)
    print(root)
    display(root->right
  end-if
end-display

For the seven-node tree above, the nodes would be printed as 3 1 4 0 5 2 6. To print a tree implemented as a List, you need to use a Stack and do a little work. I hadn’t looked at this problem in a long time so I decided to code up a demo to see if I remembered the algorithm. I did.

Displaying a tree implemented using a List in an inorder manner.

When I was a college professor I used to enjoy teaching students how to implement a tree data structure using recursion because the technique is fascinating. But I always told my students that knowing how to use recursion is fine, but in a production environment you should avoid recursion if possible — as a rule of thumb, recursive functions are tricky, error-prone, and difficult to maintain or modify.

Left: Some trees in November on the street where I live — naturally beautiful. Center: An old-style paint-by-numbers painting of trees — oddly attractive. Right: A huge alien tree on an alien world (unknown artist) — very creative.