Preorder Traversal of Binary Tree

How does Preorder Traversal of Binary Tree work?

To understand how preorder traversal works, let's consider an example binary tree:

The preorder traversal of this tree would visit the nodes in the following order: A, B, D, E, C, F.

1. We start at the root node A & process its value.
    
2. Then, we move to the left subtree rooted at B.

• We process B's value.
   
• We recursively traverse B's left subtree, which consists of node D. We process D's value.
   
• We recursively traverse B's right subtree, which consists of node E. We process E's value.
   

1. After processing the left subtree of A, we move to the right subtree rooted at C.

• We process C's value.
   
• We recursively traverse C's right subtree, which consists of node F. We process F's value.
   

The preorder traversal follows the "root-left-right" order, meaning it processes the root node first, then recursively processes the left subtree, & finally the right subtree.

Program to Implement Preorder Traversal of Binary Tree (Recursive approach):

Here's a C++ program that demonstrates the implementation of preorder traversal using a recursive approach:

• C++
• Java
• Python

C++

#include <iostream>

using namespace std;

struct Node {

    int data;

    Node* left;

    Node* right;

    Node(int value) : data(value), left(nullptr), right(nullptr) {}

};

void preorderTraversal(Node* root) {

    if (root == nullptr)

        return;

    cout << root->data << " ";

    preorderTraversal(root->left);

    preorderTraversal(root->right);

}

int main() {

    Node* root = new Node(1);

    root->left = new Node(2);

    root->right = new Node(3);

    root->left->left = new Node(4);

    root->left->right = new Node(5);

    cout << "Preorder traversal: ";

    preorderTraversal(root)

    return 0;

}

You can also try this code with Online C++ Compiler

Run Code

Java

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    void preorderTraversal(Node node) {
        if (node == null)
            return;

        System.out.print(node.data + " ");
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.print("Preorder traversal: ");
        tree.preorderTraversal(tree.root);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class Node:
    def __init__(self, item):
        self.left = None
        self.right = None
        self.val = item

def preorder(root):
    if root:
        print(str(root.val) + " ", end='')
        preorder(root.left)
        preorder(root.right)

# Creating a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Preorder traversal: ", end='')
preorder(root)

You can also try this code with Online Python Compiler

Run Code

In these programs : 

The preorder traversal of a binary tree follows a specific order: it visits the root node first, then recursively traverses the left subtree, & finally the right subtree. This process is repeated for each subtree until all nodes have been visited.

In the provided code snippets, the binary tree is represented using a Node class or struct, which contains the data stored at each node & references or pointers to its left & right child nodes.

The preorderTraversal function (or preorder in Python) takes the root node of the binary tree as input. It performs the following steps:

1. If the current node is null (or None in Python), it means the tree is empty, so the function returns.
    
2. Otherwise, it prints the value of the current node.
    
3. It recursively calls itself on the left subtree of the current node.
    
4. After exploring the left subtree, it recursively calls itself on the right subtree.
    

This recursive process continues until all nodes have been visited.

In the main function (or the main part of the code in Python), a binary tree is manually created by instantiating Node objects & linking them appropriately. The preorderTraversal function is then called with the root node to perform the preorder traversal & print the node values.

The output of the program will be:

Preorder traversal: 1 2 4 5 3

Complexity Analysis

Time Complexity

• The preorder traversal algorithm visits each node in the binary tree exactly once.
   
• For a binary tree with n nodes, the time complexity of preorder traversal is O(n) because it requires visiting all the nodes.
   
• The recursive calls & the processing of each node take constant time, so the overall time complexity is linear with respect to the number of nodes.

Space Complexity

• The space complexity of preorder traversal depends on the maximum depth of the recursive calls, which is determined by the height of the binary tree.
   
• In the worst case, when the binary tree is skewed (resembling a linked list), the recursive calls can go up to the maximum depth of the tree.
   
• The space complexity in the worst case is O(h), where h is the height of the binary tree.
   
• For a balanced binary tree, the height is typically logarithmic, resulting in a space complexity of O(log n).
   

Note: It's important to note that the space complexity is due to the recursive calls on the call stack. Each recursive call requires additional space on the stack to store the function parameters & local variables.

Use Cases of Preorder Traversal

Preorder traversal has several use cases in various scenarios. Here are a few common applications:

Copying a Binary Tree

1. Preorder traversal can be used to create a copy of a binary tree.
    
2. By visiting nodes in preorder fashion & creating new nodes with the same values, we can construct an exact replica of the original tree.
    
3. This is useful when we need to modify the tree without affecting the original structure.

Prefix Expression Evaluation

1. Preorder traversal is used to evaluate prefix expressions.
    
2. In a prefix expression, the operator precedes its operands.
    
3. By traversing the expression tree in preorder, we can evaluate the expression by applying the operators to their operands in the correct order.

Serialization & Deserialization

1. Preorder traversal is commonly used for serializing & deserializing binary trees.
    
2. Serialization is the process of converting a tree structure into a linear representation, such as a string or an array.
    
3. By traversing the tree in preorder & storing the node values, we can obtain a serialized representation of the tree.
    
4. Deserialization is the reverse process, where the serialized representation is used to reconstruct the original tree structure.

Solving Tree-based Problems

1. Many problems involving binary trees can be solved using preorder traversal.
    
2. For example, finding the maximum depth of a binary tree, checking if two trees are identical, or constructing a binary search tree from a given array.
    
3. Preorder traversal provides a way to visit nodes in a specific order, which can be useful in solving such problems efficiently.

Frequently Asked Questions

Can preorder traversal be implemented iteratively?

Yes, preorder traversal can be implemented iteratively using a stack data structure. The iterative approach follows the same order as the recursive approach but avoids the overhead of recursive function calls.

Is preorder traversal unique for a given binary tree?

Yes, the preorder traversal of a binary tree is unique. Each binary tree has a specific structure, and the preorder traversal visits the nodes in a deterministic order based on that structure.

Can preorder traversal be used for binary search trees?

Yes, preorder traversal can be used for binary search trees. However, it does not visit the nodes in a sorted order. If a sorted order is required, an inorder traversal is more suitable for binary search trees.

Conclusion

In this article, we talked about preorder traversal of binary trees. We learned about the algorithm, which visits the root node first, followed by the left subtree and then the right subtree. We implemented the preorder traversal using a recursive approach in C++, Java, and Python. We also analyzed the time and space complexity of the algorithm. Additionally, we discussed several use cases where preorder traversal is commonly applied, such as copying binary trees, evaluating prefix expressions, and solving tree-based problems. 

You can also practice coding questions commonly asked in interviews on Coding Ninjas Code360. 

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.