WikiGalaxy
Tree Inorder Traversal
Binary Tree Inorder Traversal
Understanding Inorder Traversal
Inorder traversal is a depth-first traversal technique for binary trees where the nodes are recursively visited in the order: Left, Root, Right. This method is particularly useful for binary search trees (BST) as it returns the nodes in non-decreasing order.
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
void inorderTraversal(Node node) {
if (node == null)
return;
inorderTraversal(node.left);
System.out.print(node.data + " ");
inorderTraversal(node.right);
}
}
Console Output:
1 2 3 4 5
Inorder Traversal of a BST
Inorder Traversal in BST
In a Binary Search Tree (BST), inorder traversal yields the nodes in non-decreasing order. This property is utilized in various applications such as sorting and validating the BST properties.
class BST {
Node root;
void inorderTraversal(Node node) {
if (node == null)
return;
inorderTraversal(node.left);
System.out.print(node.data + " ");
inorderTraversal(node.right);
}
}
Console Output:
10 20 30 40 50
Iterative Inorder Traversal
Iterative Approach
The iterative approach to inorder traversal uses a stack to simulate the recursive call stack. This method is useful for large trees to avoid stack overflow issues inherent in recursive methods.
class BinaryTree {
Node root;
void iterativeInorder() {
if (root == null)
return;
Stack stack = new Stack();
Node curr = root;
while (curr != null || stack.size() > 0) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
System.out.print(curr.data + " ");
curr = curr.right;
}
}
}
Console Output:
3 5 7 10 15
Inorder Traversal with Morris Method
Morris Traversal
Morris Traversal is an inorder tree traversal algorithm that does not require a stack or recursion. It uses threaded binary trees to reduce the space complexity to O(1).
class BinaryTree {
Node root;
void morrisTraversal() {
Node current, pre;
if (root == null)
return;
current = root;
while (current != null) {
if (current.left == null) {
System.out.print(current.data + " ");
current = current.right;
} else {
pre = current.left;
while (pre.right != null && pre.right != current)
pre = pre.right;
if (pre.right == null) {
pre.right = current;
current = current.left;
} else {
pre.right = null;
System.out.print(current.data + " ");
current = current.right;
}
}
}
}
}
Console Output:
2 4 6 8 10
Inorder Traversal for N-ary Tree
N-ary Tree Traversal
Inorder traversal for N-ary trees is less common as it is primarily used for binary trees. However, when applied, it involves visiting the leftmost child first, then the root, and proceeding to the right siblings.
class NaryNode {
int data;
List children;
NaryNode(int data) {
this.data = data;
this.children = new ArrayList<>();
}
}
class NaryTree {
NaryNode root;
void inorderTraversal(NaryNode node) {
if (node == null)
return;
for (int i = 0; i < node.children.size(); i++) {
inorderTraversal(node.children.get(i));
if (i == 0) {
System.out.print(node.data + " ");
}
}
}
}
Console Output:
Child1 Root Child2
