The tree data structure that we will be traversing is as shown below:
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
Thank you for reading. Feel free to contact me if you have any question, comment or suggestion.
🎉
