WikiGalaxy
Tree Traversal Overview
In-order Traversal
Description:
In-order traversal visits the left subtree, the root, and then the right subtree. This traversal method results in visiting nodes in non-decreasing order for a binary search tree.
void inOrder(Node node) {
if (node == null)
return;
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
Console Output:
1 2 3 4 5
Pre-order Traversal
Description:
Pre-order traversal visits the root, the left subtree, and then the right subtree. This method is used to create a copy of the tree.
void preOrder(Node node) {
if (node == null)
return;
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
Console Output:
3 2 1 4 5
Post-order Traversal
Description:
Post-order traversal visits the left subtree, the right subtree, and then the root. This method is useful for deleting the tree.
void postOrder(Node node) {
if (node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.print(node.data + " ");
}
Console Output:
1 2 5 4 3
Level-order Traversal
Description:
Level-order traversal visits nodes level by level from left to right. It uses a queue to traverse the tree.
void levelOrder(Node root) {
if (root == null)
return;
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node tempNode = queue.poll();
System.out.print(tempNode.data + " ");
if (tempNode.left != null)
queue.add(tempNode.left);
if (tempNode.right != null)
queue.add(tempNode.right);
}
}
Console Output:
3 2 4 1 5
Reverse Level-order Traversal
Description:
Reverse level-order traversal visits nodes from bottom to top, level by level, and from right to left. It utilizes a queue and a stack to achieve this order.
void reverseLevelOrder(Node root) {
if (root == null)
return;
Queue queue = new LinkedList<>();
Stack stack = new Stack<>();
queue.add(root);
while (!queue.isEmpty()) {
Node tempNode = queue.poll();
stack.push(tempNode);
if (tempNode.right != null)
queue.add(tempNode.right);
if (tempNode.left != null)
queue.add(tempNode.left);
}
while (!stack.isEmpty()) {
Node node = stack.pop();
System.out.print(node.data + " ");
}
}
Console Output:
1 5 2 4 3
