Preorder traversal of a binary tree

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

Recursive algorithm:

1. Check if the current node is empty or null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-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 preorder 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 preorder(Node root){
        if(root == null){
            return;
        }
        //Traverse root        

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

        preorder(root.left);
        //Traverse right subtree        

        preorder(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().preorder(node1);
    }
}