Table of contents

Preorder Traversal of a Binary Tree

GIven a binary tree, the task is to print the Pre-order Traversal of the given tree.

Preorder traversal is a depth-first traversal technique for binary trees where the root node is processed first, followed by the left subtree and then the right subtree. The traversal follows the order:

  1. Visit the root node.
  2. Traverse the left subtree.
  3. Traverse the right subtree.

Preorder traversal is called so because the root is visited before the subtrees, making it a "pre-order" visit.

Example of Preorder Traversal

plaintext
Input:  
        1
       / \
      2   3
     / \
    4   5
        
Output: 1, 2, 4, 5, 3

The preorder traversal for this tree is:

  1. First, visit the root node 1.
  2. Then, traverse the left subtree of 1, which starts at 2.
  3. Visit the root node of this subtree, which is 2.
  4. Traverse the left subtree of 2, which is 4 (a leaf node).
  5. Traverse the right subtree of 2, which is 5 (a leaf node).
  6. Finally, traverse the right subtree of 1, which is 3 (a leaf node).

The preorder traversal of this tree is: 1, 2, 4, 5, 3.

Preorder Traversal Rules

In Preorder traversal, the following steps are performed recursively:

  1. Visit the root node (process the current node).
  2. Traverse the left subtree by recursively performing a preorder traversal on it.
  3. Traverse the right subtree by recursively performing a preorder traversal on it.

The traversal order is root → left → right.

Here are the implementations of preorder traversal in C++, Java, and Python.

C++ Program to print the Preorder traversal of a Binary Tree

cpp
#include <iostream>
using namespace std;

// Definition of a tree node
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = right = nullptr;
    }
};

// Function for preorder traversal (root, left, right)
void preorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }

    // Visit the root node
    cout << root->data << " ";

    // Traverse the left subtree
    preorderTraversal(root->left);

    // Traverse the right subtree
    preorderTraversal(root->right);
}

// Main function
int main() {
    // Construct the binary tree
    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);

    // Perform preorder traversal
    cout << "Preorder Traversal: ";
    preorderTraversal(root);

    return 0;
}

Java Program to print the Preorder traversal of a Binary Tree

java
// Definition of a tree node
class Node {
    int data;
    Node left, right;

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

public class Main {
    // Function for preorder traversal (root, left, right)
    public static void preorderTraversal(Node root) {
        if (root == null) {
            return;
        }

        // Visit the root node
        System.out.print(root.data + " ");

        // Traverse the left subtree
        preorderTraversal(root.left);

        // Traverse the right subtree
        preorderTraversal(root.right);
    }

    public static void main(String[] args) {
        // Construct the binary tree
        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);

        // Perform preorder traversal
        System.out.print("Preorder Traversal: ");
        preorderTraversal(root);
    }
}

Python Program to print the Preorder Traversal of a Binary Tree

python
# Definition of a tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function for preorder traversal (root, left, right)
def preorder_traversal(root):
    if root is None:
        return

    # Visit the root node
    print(root.data, end=" ")

    # Traverse the left subtree
    preorder_traversal(root.left)

    # Traverse the right subtree
    preorder_traversal(root.right)

# Main function
if __name__ == "__main__":
    # Construct the binary tree
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)

    # Perform preorder traversal
    print("Preorder Traversal: ", end="")
    preorder_traversal(root)

Properties of Preorder Traversal

  • Time Complexity: O(n), where n is the number of nodes in the tree, because each node is visited exactly once.
  • Space Complexity: O(h), where h is the height of the tree. The space complexity is due to the recursion stack.
  • Traversal Order: In Preorder traversal, the root node is processed before its child nodes.

When to Use Preorder Traversal ?

Preorder traversal is particularly useful when you need to:

  • Copy a tree: Preorder traversal can be used to create a copy of a binary tree.
  • Serialize a tree: In tree serialization, preorder traversal is often used because it processes the root before the subtrees, ensuring that the tree structure is maintained when reconstructing the tree.
  • Generate Polish Notation: Preorder traversal can be used to generate the prefix expression of an expression tree, often used in compilers and interpreters.

DSA

Related Articles