How to Do Postorder Traversal in a Binary Tree in Java

Though Java doesn't provide a binary tree class in the default libraries, a basic binary tree class is simple enough to be presented. A "traversal" of a data structure is an algorithm that visits each node once. This is often implemented as some sort of iterator (much like a list iterator) or method that will call a callback method for each node. In Java, to do a "postorder" traversal which will visit the root node last, no callbacks or iterators are necessary. The traversal function will simply print each node it visits to the console.

Difficulty:

Moderate

Instructions

1. Write a basic binary search tree class. There are only two methods that need to be supported at this stage: a basic constructor that initializes the node's value, and an insert method. The insert method will traverse a tree and create a new node in the correct place. ""public class BinaryTree {
BinaryTree left;
BinaryTree right;
int value;

public BinaryTree(int v) {
value = v;
}

// Insert a value into the tree
public void insert(int v) {
if(v < value) {
if(left == null)
left = new BinaryTree(v);
else
left.insert(v);
}

else if(v > value) {
if(right == null)
right = new BinaryTree(v);
else
right.insert(v);
}
}""

2. Create an instance of the binary tree which will be the root node. Every node, even the root node, must have a value.

3. Choose a value for the root node that's somewhere in the middle of the objects you'll be storing. For example, if you're storing an even distribution of numbers from 1 to 100, 50 is a good choice for the root node. Binary trees should be as balanced as possible, since unbalanced trees grow extremely tall and aren't very effective.""BinaryTree b = new BinaryTree(50);""

4. Insert some nodes into the tree. Since this tree is not auto-balancing, to retain balance, nodes should be inserted in a specific order. The order in this example code is crafted to make the shortest and most efficient tree possible.""b.insert(20);
b.insert(40);
b.insert(10);
b.insert(5);
b.insert(45);

b.insert(70);
b.insert(60);
b.insert(80);
b.insert(55);
b.insert(85);""

5. Traverse the tree, traversing the left tree first, followed by the right tree, and then finally the root node. If recursion is used to do the postorder traversal, the method is only three lines long. In this case, the stack will only grow to the height of the tree. Since the tree is balanced and small, recursion won't overflow the stack.

6. Add new method to the BinaryTree class called postorder. Here, it only prints the value of each node it visits.""public void postorder() {
if(left != null) left.postorder();
if(right != null) right.postorder();
System.out.println(value);
}""

7. Print the nodes in postorder by calling the b.postorder method after your inserts.
   
   ""b.postorder();"

Tips & Warnings

• Since recursion takes stack space, it should be used carefully. If your binary tree is very large, the traversal function should be implemented iteratively.

• The more complicated "delete node" method isn't supported by this example class.