Tree Traversal Algorithms in Java - OOP | Mike CK - Electrical Engineer and Developer

The tree data structure that we will be traversing is as shown below: A Tree Data Structure

You first need to represent the tree data structure. We will use a class that will be a template of all the nodes that we will need:

1
2
3
4
5
6


// define the Node class
class Node{
    public int root;
    public Node right;
    public Node left;
}

Next, we will need to initialize and connect the nodes to form a tree as shown in the figure above:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


// initialise nodes
Node node1 = new Node();
node1.root = 5;

Node node2 = new Node();
node2.root = 4;

Node node3 = new Node();
node3.root = 6;

Node node4 = new Node();
node4.root = 1;

Node node5 = new Node();
node5.root = 2;

#connect the nodes
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;

We are now ready to implement any of the tree traversal algorithms.

make sure to import ArrayList from java.util.ArrayList.

Pre Order Traversal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// the preOrder function, that is, it returns starting from the root, then left, then right
static ArrayList<Integer> preOrder(Node node, ArrayList<Integer> nodes){
    nodes.add(node.root);
    if(node.root != 0 && node.left != null) {
        preOrder(node.left, nodes);
    }
    if (node.root != 0 && node.right != null) {
        preOrder(node.right, nodes);
    }
    return nodes;
}

In Order Traversal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// the inOrder function, returns the left, then root, then right
static ArrayList<Integer> inOrder(Node node, ArrayList<Integer> nodes){
    if(node.root != 0 && node.left != null) {
        inOrder(node.left, nodes);
    }
    nodes.add(node.root);
    if (node.root != 0 && node.right != null) {
        inOrder(node.right, nodes);
    }
    return nodes;
}

Post Order Traversal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// the postOrder function returns the left, the right then the root
static ArrayList<Integer> postOrder(Node node, ArrayList<Integer> nodes){
    if(node.root != 0 && node.left != null) {
        postOrder(node.left, nodes);
    }
    if (node.root != 0 && node.right != null) {
        postOrder(node.right, nodes);
    }
    nodes.add(node.root);
    return nodes;
}

Calling the various functions within main

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


ArrayList<Integer> result = new ArrayList<Integer>();

result = preOrder(node1, result);
System.err.println(result);

result.clear();
result = inOrder(node1, result);
System.err.println(result);

result.clear();
result = postOrder(node1, result);
System.err.println(result);

The complete tree traversal algorithms code in Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80


import java.util.ArrayList;

//the node class has a root, left, and right fields
class Node{
    public int root;
    public Node right;
    public Node left;
}

class Tree{
    public static void main(String[] args){
        Node node1 = new Node();
        node1.root = 5;

        Node node2 = new Node();
        node2.root = 4;

        Node node3 = new Node();
        node3.root = 6;

        Node node4 = new Node();
        node4.root = 1;

        Node node5 = new Node();
        node5.root = 2;

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;

        ArrayList<Integer> result = new ArrayList<Integer>();

        result = preOrder(node1, result);
        System.err.println(result);

        result.clear();
        result = inOrder(node1, result);
        System.err.println(result);

        result.clear();
        result = postOrder(node1, result);
        System.err.println(result);
    }

    //static methods so as to simply call without creating objects...

    static ArrayList<Integer> preOrder(Node node, ArrayList<Integer> nodes){
        nodes.add(node.root);
        if(node.root != 0 && node.left != null) {
            preOrder(node.left, nodes);
        }
        if (node.root != 0 && node.right != null) {
            preOrder(node.right, nodes);
        }
        return nodes;
    }

    static ArrayList<Integer> inOrder(Node node, ArrayList<Integer> nodes){
        if(node.root != 0 && node.left != null) {
            inOrder(node.left, nodes);
        }
        nodes.add(node.root);
        if (node.root != 0 && node.right != null) {
            inOrder(node.right, nodes);
        }
        return nodes;
    }

    static ArrayList<Integer> postOrder(Node node, ArrayList<Integer> nodes){
        if(node.root != 0 && node.left != null) {
            postOrder(node.left, nodes);
        }
        if (node.root != 0 && node.right != null) {
            postOrder(node.right, nodes);
        }
        nodes.add(node.root);
        return nodes;
    }
}

The output:

[Running] cd "/Users/mikeck/Desktop/Java/" && javac Tree.java && java Tree
[5, 4, 1, 2, 6]
[1, 4, 2, 5, 6]
[1, 2, 4, 6, 5]

[Done] exited with code=0 in 4.213 seconds