Tree Traversal

Creating a Tree

The previous page showed how to store a Tree in Nodes and in an Array. But how do you convert a Tree from an Array to the more-standard Node form?

Make sure you have your basic Node class, as covered before. Then follow these steps:

1. Create a Node node from a given cell i in the array: Node node = new Node(ar[i]);
2. Create the children Nodes from their positions in the array. (See step #1).
3. Assign the children Nodes to node.left and node.right.

You first create a Node, and then you create children Nodes in the same manner. This sounds like a recursive function will be needed! As mentioned, since trees are recursive structures, recursive functions are used to navigate them.

Here's the above algorithm in Java:

static Node arrayToTree(int[] ar, int i){
    if(i >= ar.length || ar[i]==0)
        return null;

    Node node = new Node(ar[i]);
    node.left = arrayToTree(ar, 2*i+1);
    node.right = arrayToTree(ar, 2*i+2);
    return node;
}

Traversing a Tree

To find information in a Node Tree, you need to traverse through it, which means to go through all its Nodes systematically. There are different orders you can use to go through a tree. Pre-order traversal means you process a Node and then process its sub-trees.