Java How to perform in-order traversal of a binary tree?

To perform an in-order traversal of a binary tree in Java, you can use a recursive or an iterative approach.

Here is an example of how you can perform an in-order traversal of a binary tree in Java using a recursive approach:

public void inOrderTraversal(Node node) {
    if (node != null) {
        inOrderTraversal(node.left);
        System.out.print(node.data + " ");
        inOrderTraversal(node.right);
    }
}

In this example, the inOrderTraversal method takes a Node object as an argument and performs an in-order traversal of the binary tree. The method starts by visiting the left child of the node, then it prints the data of the node, and finally it visits the right child of the node.

The in-order traversal algorithm visits the nodes of the tree in the following order: left child, node, right child. This means that the nodes are visited in ascending order if the tree is a binary search tree.

The time complexity of the in-order traversal algorithm is O(n), where n is the number of nodes in the tree. The space complexity is O(h), where h is the height of the tree, because the algorithm uses a constant amount of space for each level of the tree.

Here is an example of how you can perform an in-order traversal of a binary tree in Java using an iterative approach:

public void inOrderTraversalIterative(Node root) {
    Stack<Node> stack = new Stack<>();
    Node current = root;
    
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        System.out.print(current.data + " ");
        current = current.right;
    }
}

In this example, the inOrderTraversalIterative method takes a Node object as an argument and performs an in-order traversal of the binary tree using a stack data structure. The method starts by pushing the root node to the stack and moving to the left child of the node.

Then, it enters a loop that continues until the current node is null and the stack is empty. In each iteration of the loop, the method pushes the left child of the current node to the stack and moves to the left child of the node. When the current node is null, the method pops the top node from the stack, prints its data, and moves to the right child of the node.

The time complexity of the in-order traversal algorithm is O(n), where n is the number of nodes in the tree. The space complexity is O(h), where h is the height of the tree, because the algorithm uses a stack to store the nodes.

Keep in mind that these are just two examples of how you can perform an in-order traversal of a binary tree in Java. You can use different techniques and data structures to achieve the same result, such as using a queue data structure or a Morris traversal algorithm.