Skip to content

Instantly share code, notes, and snippets.

@ssaurel

ssaurel/Tree.java

Last active Apr 9, 2019
Embed
What would you like to do?
Tree Traversal Algorithms Implementations in Java on the SSaurel's Channel
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Tree {
// Root, Left, Right
public static < T > void preOrderTraverse(Node < T > node) {
if (node == null)
return;
System.out.print(node.data + " ");
preOrderTraverse(node.left);
preOrderTraverse(node.right);
}
public static < T > void iterativePreOrderTraverse(Node < T > node) {
if (node == null)
return;
// We create an empty stack and we push root to it
Stack < Node < T >> nodeStack = new Stack < > ();
nodeStack.push(node);
// We pop all items one by one.
// For each item, we make the following steps : print data, push its right child, push its left child
// We push right child in first for that left is processed first
while (!nodeStack.empty()) {
Node < T > currentNode = nodeStack.pop();
System.out.print(currentNode.data + " ");
if (currentNode.right != null)
nodeStack.push(currentNode.right);
if (currentNode.left != null)
nodeStack.push(currentNode.left);
}
}
// Left, Root, Right
public static < T > void inOrderTraverse(Node < T > node) {
if (node == null)
return;
inOrderTraverse(node.left);
System.out.print(node.data + " ");
inOrderTraverse(node.right);
}
public static < T > void iterativeInOrderTraverse(Node < T > node) {
if (node == null)
return;
// We create an empty stack
Stack < Node < T >> nodeStack = new Stack < > ();
Node < T > currentNode = node;
// We traverse the tree
while (currentNode != null || nodeStack.size() > 0) {
// We try to reach the most left node of the current node
while (currentNode != null) {
// We add the pointer to the stack before traversing to the left node
nodeStack.push(currentNode);
currentNode = currentNode.left;
}
// Current Node is null a this point
currentNode = nodeStack.pop();
System.out.print(currentNode.data + " ");
// Now, it's time to visit the right subtree
currentNode = currentNode.right;
}
}
// Left, Right, Root
public static < T > void postOrderTraverse(Node < T > node) {
if (node == null)
return;
postOrderTraverse(node.left);
postOrderTraverse(node.right);
System.out.print(node.data + " ");
}
public static < T > void iterativePostOrderTraverse(Node < T > node) {
if (node == null)
return;
// We create two stacks
Stack < Node < T >> nodeStack1 = new Stack < > ();
Stack < Node < T >> nodeStack2 = new Stack < > ();
// We push root to first stack
nodeStack1.push(node);
// We iterate while first stack is not empty
while (!nodeStack1.isEmpty()) {
// We pop an item from nodeStack1 and we push it to nodeStack2
Node < T > tmpNode = nodeStack1.pop();
nodeStack2.push(tmpNode);
// We push left and right children of removed item to nodeStack1
if (tmpNode.left != null)
nodeStack1.push(tmpNode.left);
if (tmpNode.right != null)
nodeStack1.push(tmpNode.right);
}
// We print all elements of nodeStack2
while (!nodeStack2.isEmpty()) {
Node < T > tmpNode = nodeStack2.pop();
System.out.print(tmpNode.data + " ");
}
}
// Level traversal (Breadth-first search)
public static < T > void levelOrderTraverse(Node < T > node) {
if (node == null)
return;
Queue < Node < T >> queue = new LinkedList < > ();
// we add start node
queue.add(node);
// iterate while queue not empty
while (!queue.isEmpty()) {
// dequeue and print data
Node < T > next = queue.remove();
System.out.print(next.data + " ");
// we add children nodes if not null
if (next.left != null)
queue.add(next.left);
if (next.right != null)
queue.add(next.right);
}
}
public static void main(String[] args) {
// We create the nodes of our tree
Node < String > A = new Node < String > ("A");
Node < String > B = new Node < String > ("B");
Node < String > C = new Node < String > ("C");
Node < String > D = new Node < String > ("D");
Node < String > E = new Node < String > ("E");
Node < String > F = new Node < String > ("F");
Node < String > G = new Node < String > ("G");
Node < String > H = new Node < String > ("H");
Node < String > I = new Node < String > ("I");
Node < String > J = new Node < String > ("J");
Node < String > K = new Node < String > ("K");
// Root and building of the tree
Node < String > root = A;
A.left = B;
A.right = C;
B.left = D;
B.right = E;
D.left = H;
D.right = I;
E.left = J;
C.left = F;
C.right = G;
G.left = K;
System.out.println("Pre Order Traversal");
preOrderTraverse(root);
System.out.println("\n");
System.out.println("Iterative Pre Order Traversal");
iterativePreOrderTraverse(root);
System.out.println("\n");
System.out.println("========");
System.out.println();
System.out.println("In Order Traversal");
inOrderTraverse(root);
System.out.println("\n");
System.out.println("Iterative In Order Traversal");
iterativeInOrderTraverse(root);
System.out.println("\n");
System.out.println("========");
System.out.println();
System.out.println("Post Order Traversal");
postOrderTraverse(root);
System.out.println("\n");
System.out.println("Iterative Post Order Traversal");
iterativePostOrderTraverse(root);
System.out.println("\n");
System.out.println("========");
System.out.println();
System.out.println("Level Order Traversal");
levelOrderTraverse(root);
System.out.println("\n");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.