Tree Traversal

Tree traversal is the process of visiting each node in a tree data structure in a specific order. It allows us to access the data stored in each node of the tree.

There are three main types of tree traversal: in-order traversal, pre-order traversal, and post-order traversal.

In-order Traversal

In in-order traversal, the left subtree is visited first, followed by the root node, and then the right subtree. It produces sorted output when applied to a binary search tree (BST).

Here's the recursive implementation of in-order traversal in Java:

{{code}}

The inOrderTraversal function takes a tree node as input and performs in-order traversal by recursively traversing the left subtree, visiting the root node, and then recursively traversing the right subtree. The data of each visited node is printed.

Pre-order Traversal

In pre-order traversal, the root node is visited first, followed by the left subtree, and then the right subtree. It is useful for creating a copy of the tree.

Post-order Traversal

In post-order traversal, the left subtree is visited first, followed by the right subtree, and then the root node. It is useful for deleting the nodes of a tree.

Try implementing and running the in-order traversal function on a binary tree to see the order in which the nodes are visited and their corresponding data.

xxxxxxxxxx

// Binary Tree Node

class Node {

    int data;

    Node left, right;

​

    public Node(int item) {

        data = item;

        left = right = null;

    }

}

​

// In-order traversal

void inOrderTraversal(Node node) {

    if (node != null) {

        inOrderTraversal(node.left);

        System.out.print(node.data + " ");

        inOrderTraversal(node.right);

    }

}