Inorder traversal of a binary tree

Inorder tree traversal is a traversal method for binary tree where we traverse left subtree first and then node and right subtree after that. This algorithm can be implemented recursively as well as using iterative method. Following diagram shows inorder traversal:

Recursive algorithm:

1. Check if the current node is empty or null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

Time Complexity:

Since, we visit every node only once, time complexity is proportional to number of nodes in binary tree.

So, Time Complexity of Inorder traversal is - O(n)

Java Solution:

public class TreeTraversal {

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

    public void inorder(Node root){
        if(root == null){
            return;
        }
        //Traverse left subtree        

        inorder(root.left);
        System.out.print(root.data + " ");
        //Traverse right subtree        

        inorder(root.right);
    }

    public static void main(String[] args) {
        //Build Tree        

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        new TreeTraversal().inorder(node1);
    }
}