Preorder Traversal

Preorder traversal visits the node in the order: Root -> Left -> Right

Algorithm for Preorder Traversal:

Preorder(tree)

Visit the root.
Traverse the left subtree, i.e., call Preorder(left->subtree)
Traverse the right subtree, i.e., call Preorder(right->subtree)

Uses of Preorder Traversal:

Preorder traversal is used to create a copy of the tree.
Preorder traversal is also used to get prefix expressions on an expression tree.

Code Snippet for Preorder Traversal:

C++

// Given a binary tree, print its nodes in preorder
void printPreorder(struct Node* node)
{
    if (node == NULL)
        return;

    // First print data of node
    cout << node->data << " ";

    // Then recur on left subtree
    printPreorder(node->left);

    // Now recur on right subtree
    printPreorder(node->right);
}

// Given a binary tree, print its nodes in preorder
void printPreorder(struct node* node)
{
    if (node == NULL)
        return;

    // First print data of node
    printf("%d ", node->data);

    // Then recur on left subtree
    printPreorder(node->left);

    // Now recur on right subtree
    printPreorder(node->right);
}

Java

// Given a binary tree, print its nodes in preorder
void printPreorder(Node node)
{
    if (node == null)
        return;

    // First print data of node
    System.out.print(node.key + " ");

    // Then recur on left subtree
    printPreorder(node.left);

    // Now recur on right subtree
    printPreorder(node.right);
}

Python3

# A function to do preorder tree traversal
def printPreorder(root):

    if root:

        # First print the data of node
        print(root.val, end=" "),

        # Then recur on left child
        printPreorder(root.left)

        # Finally recur on right child
        printPreorder(root.right)

// Given a binary tree, print
// its nodes in preorder
void printPreorder(Node node)
{
    if (node == null)
        return;

    // First print data of node
    Console.Write(node.key + " ");

    // Then recur on left subtree
    printPreorder(node.left);

    // Now recur on right subtree
    printPreorder(node.right);
}

Javascript

// Given a binary tree, print its nodes in preorder
function printPreorder(node) {
    if (node == null)
        return;

    // First print data of node
    document.write(node.key + " ");

    // Then recur on left subtree
    printPreorder(node.left);

    // Now recur on right subtree
    printPreorder(node.right);
}

Output

Preorder traversal of binary tree is 
1 2 4 5 3

Time Complexity: O(N)
Auxiliary Space: If we don’t consider the size of the stack for function calls then O(1) otherwise O(h) where h is the height of the tree.

Tree Traversal Techniques – Data Structure and Algorithm Tutorials

Tree Traversal techniques include various ways to visit all the nodes of the tree. Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. In this article, we will discuss about all the tree traversal techniques along with their uses.

Table of Content

Tree Traversal Meaning
Tree Traversal Techniques
Inorder Traversal
Preorder Traversal
Postorder Traversal
Level Order Traversal
Other Tree Traversals
Frequently Asked Questions (FAQs) on Tree Traversal Techniques

Preorder Traversal

Tree Traversal Techniques – Data Structure and Algorithm Tutorials

Similar Reads

Contact Us