Tree Traversal Algorithm
The Tree Traversal Algorithm is a fundamental technique used in computer science to traverse or visit nodes in a tree data structure systematically. Trees are non-linear data structures that consist of elements called nodes, connected by edges to form a hierarchical structure. The traversal algorithm aims to process each node in the tree exactly once in a specific order, according to the nature of the traversal. There are three common types of tree traversal algorithms: in-order, pre-order, and post-order, which are primarily used in binary trees where each node has at most two children.
In-order traversal processes nodes in a left-root-right order, meaning it first visits the left subtree, then the root node, and finally the right subtree. Pre-order traversal follows a root-left-right pattern, processing the root node before traversing the left and right subtrees. Post-order traversal operates in a left-right-root sequence, visiting the left subtree, right subtree, and then the root node. These traversal algorithms are essential in various applications, such as searching for specific elements in the tree, manipulating tree structures, or performing operations on tree elements. By efficiently traversing trees, programmers can optimize data processing, ensuring both accurate results and optimal performance.
package DataStructures.Trees;
import java.util.LinkedList;
/**
* @author Varun Upadhyay (https://github.com/varunu28)
*/
// Driver Program
public class TreeTraversal {
public static void main(String[] args) {
Node tree = new Node(5);
tree.insert(3);
tree.insert(2);
tree.insert(7);
tree.insert(4);
tree.insert(6);
tree.insert(8);
// Prints 5 3 2 4 7 6 8
System.out.println("Pre order traversal:");
tree.printPreOrder();
System.out.println();
// Prints 2 3 4 5 6 7 8
System.out.println("In order traversal:");
tree.printInOrder();
System.out.println();
// Prints 2 4 3 6 8 7 5
System.out.println("Post order traversal:");
tree.printPostOrder();
System.out.println();
// Prints 5 3 7 2 4 6 8
System.out.println("Level order traversal:");
tree.printLevelOrder();
System.out.println();
}
}
/**
* The Node class which initializes a Node of a tree
* Consists of all 4 traversal methods: printInOrder, printPostOrder， printPreOrder & printLevelOrder
* printInOrder: LEFT -> ROOT -> RIGHT
* printPreOrder: ROOT -> LEFT -> RIGHT
* printPostOrder: LEFT -> RIGHT -> ROOT
* printLevelOrder: Prints by level (starting at root), from left to right.
*/
class Node {
Node left, right;
int data;
public Node(int data) {
this.data = data;
}
public void insert(int value) {
if (value < data) {
if (left == null) {
left = new Node(value);
} else {
left.insert(value);
}
} else {
if (right == null) {
right = new Node(value);
} else {
right.insert(value);
}
}
}
public void printInOrder() {
if (left != null) {
left.printInOrder();
}
System.out.print(data + " ");
if (right != null) {
right.printInOrder();
}
}
public void printPreOrder() {
System.out.print(data + " ");
if (left != null) {
left.printPreOrder();
}
if (right != null) {
right.printPreOrder();
}
}
public void printPostOrder() {
if (left != null) {
left.printPostOrder();
}
if (right != null) {
right.printPostOrder();
}
System.out.print(data + " ");
}
/**
* O(n) time algorithm.
* Uses O(n) space to store nodes in a queue to aid in traversal.
*/
public void printLevelOrder() {
LinkedList<Node> queue = new LinkedList<>();
queue.add(this);
while (queue.size() > 0) {
Node head = queue.remove();
System.out.print(head.data + " ");
// Add children of recently-printed node to queue, if they exist.
if (head.left != null) {
queue.add(head.left);
}
if (head.right != null) {
queue.add(head.right);
}
}
}
}
