Tree Traversal

Tree traversal refers to the process of visiting all the nodes of a tree in a specific order. There are three main techniques for tree traversal:

1. Preorder Traversal: Visiting the current node first, then traversing the left subtree, and finally the right subtree.

2. Inorder Traversal: Traversing the left subtree first, then visiting the current node, and finally the right subtree.

3. Postorder Traversal: Traversing the left subtree first, then the right subtree, and finally visiting the current node.

These traversal techniques can be used to perform various operations on tree nodes, such as printing the node values, searching for a specific value, or evaluating an expression tree.

Here's an example of performing an inorder traversal on a binary tree using recursion in Java:

1class Node {
2    int value;
3    Node left;
4    Node right;
5
6    public Node(int value) {
7        this.value = value;
8        left = null;
9        right = null;
10    }
11}
12
13public class TreeTraversal {
14    public static void inorderTraversal(Node root) {
15        if (root == null) {
16            return;
17        }
18
19        inorderTraversal(root.left);
20        System.out.print(root.value + " ");
21        inorderTraversal(root.right);
22    }
23
24    public static void main(String[] args) {
25        Node root = new Node(1);
26        root.left = new Node(2);
27        root.right = new Node(3);
28        root.left.left = new Node(4);
29        root.left.right = new Node(5);
30
31        System.out.println("Inorder Traversal:");
32        inorderTraversal(root);
33    }
34}

In this example, we define a Node class to represent a binary tree node. We then create a method inorderTraversal to perform the inorder traversal recursively. We start by checking if the current node is null, and if not, we recursively traverse the left subtree, visit the current node, and then traverse the right subtree. Finally, we print the value of each visited node in the inorder traversal order.

By understanding different traversal techniques, you can effectively navigate and process the nodes of a tree based on your specific requirements and algorithms.