Java Language Traversing a Tree data structure with recursion


Example

Consider the Node class having 3 members data, left child pointer and right child pointer like below.

public class Node {
    public int data;
    public Node left;
    public Node right;
    
    public Node(int data){
        this.data = data;
    }
}

We can traverse the tree constructed by connecting multiple Node class's object like below, the traversal is called in-order traversal of tree.

public static void inOrderTraversal(Node root) {
        if (root != null) {          
            inOrderTraversal(root.left); // traverse left sub tree
            System.out.print(root.data + " "); // traverse current node
            inOrderTraversal(root.right); // traverse right sub tree
        }
    }

As demonstrated above, using recursion we can traverse the tree data structure without using any other data structure which is not possible with the iterative approach.