Preorder Traversal

A Depth-First Search Method for Visiting Root First in Trees

Introduction

Preorder Traversal is a tree traversal method where the root is visited first, followed by the left subtree and then the right subtree. It's commonly used when the root needs to be processed before its children.

Preorder Traversal visits the node in the order: root->left->right

How Preorder Traversal Works?

1

Visit Root

  • The root node of the tree is visited first before any other nodes.
2

Traverse Left Subtree

  • The left subtree is then recursively traversed in the same manner (root → left → right).
3

Traverse Right Subtree

  • After the left subtree, the right subtree is recursively traversed, following the same root-first order.

Implementation of Preorder Traversal

//preorderTraversal.cpp
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *left;
Node *right;
Node(int data)
{
    this->data = data;
    this->left = NULL;
    this->right = NULL;
}
};
Node *buildTree(Node *root)
{
cout << "Enter The data: " << endl;
int data;
cin >> data;
root = new Node(data);
if (data == -1)
{
    return NULL;
}
cout << "Enter data for left : " << endl;
root->left = buildTree(root->left);
cout << "Enter data for right: " << endl;
root->right = buildTree(root->right);
return root;
}
void preorder(Node *root)
{
if (!root)
    return;
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
int main()
{
// creating tree
Node *root = NULL;
root = buildTree(root);

// preorder order
preorder(root);
}

Time Complexity

Time Complexity: O(n)

  • The function visits each node in the tree exactly once. Given that there are n nodes, the function performs n operations, resulting in O(n) time complexity.

Space Complexity

Space Complexity:O(h),where h is the height of the tree.