Preorder Traversal of Binary Tree - Recursive

In this tutorial, we will see preorder traversal of a binary tree with the help of recursion. Preorder traversal uses DFS(depth-first-search) approach to traverse the whole tree. In Preorder traversal, we firstly print the node and then go to left of the tree and at last we go to the right of the tree with the help of recursion whole tree is traversed.
Preorder Traversal: Root Left Right.

Let us take an example.

The Preorder Traversal of above given Binary Tree will be: 2, 5, 6, 7, 10, 20, 30

Explanation:

1. If we encounter any node which is null we will return back (this will be the base condition)
2. Print the node value firstly
3. Then recur to the left subtree using node.left
4. Then recur to the right subtree using node.right
The same process gets repeated until whole tree is traversed.

Algorithm:

1. if (node == null) return
2. print the node.
3. visit the left subtree.
4. visit the right subtree.

Recursive code of Preorder Traversal is implemented below:

• Java

public class Preorder {

    public static class Node {

        int val;

        Node left, right;

        // Constructor

        Node(int val) {

            this.val = val;

            left = right = null;

        }

    }

    public static void main(String[] args) {

        /*

         * Creating Binary Tree The created binary tree is same as in the above given

         * figure (refer figure for reference)

         */

        Node root = new Node(2);

        root.left = new Node(5);

        root.right = new Node(10);

        root.left.left = new Node(6);

        root.left.right = new Node(7);

        root.right.left = new Node(20);

        root.right.right = new Node(30);

        // calling preorder method

        System.out.print("Preorder Traversal is: ");

        preorder(root);

    }

    public static void preorder(Node node) {

        if (node == null)

            return;

        // Printing the node

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

        // recur to the left subtree

        preorder(node.left);

        // recur to the right subtree

        preorder(node.right);

    }

}

Output:

Preorder Traversal is: 2 5 6 7 10 20 30

Complexity Analysis:

Time Complexity: O(n), where n is number of nodes in tree. This is because, we are traversing the each node of tree at once.

Space Complexity: We have not used any extra space for storing the nodes values, so O(1) can be considered as space complexity.

---

Also See:

1. Inorder Traversal using Recursion.
2. Postorder Traversal using Recursion.