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.

This is the data of the above tree printed in pre-order:

10 1 3 4 2 5 6

Converting the above algorithm to code is straightforward.

public static void preOrder(Node node)
{
    if(node == null)
        return;
    
    System.out.print(node.getData()+" ");
    preOrder(node.left);
    preOrder(node.right);
}

A Post-order traversal is similar to a pre-order, but you visit or print the Child Node before the parent Node. This means the above tree will be printed in the following order:

3 4 1 5 6 2 10