DSA Pre-order Traversal

DSA Pre-order Traversal – Complete Beginner Guide

(Concept • Steps • Example • Code • Complexity)

Pre-order Traversal is one of the Depth-First Search (DFS) techniques used to traverse a Binary Tree.

1️⃣ What is Pre-order Traversal?

In Pre-order Traversal, nodes are visited in this order:

Root → Left → Right

The root node is visited first, before its children.

2️⃣ Simple Rule to Remember

Or simply:

3️⃣ Pre-order Traversal – Step by Step

Example Binary Tree

Traversal Order

Visit 1 (root)
Go left → 2
Go left → 4
Back → 5
Go right → 3

Output

4️⃣ Pre-order Traversal Algorithm

Visit the root node
Traverse the left subtree
Traverse the right subtree

5️⃣ Pseudocode

6️⃣ Pre-order Traversal – Recursive Code (C++)

7️⃣ Complete Example Program (C++)

#include <iostream>
using namespace std;struct Node {
int data;
Node* left;
Node* right;
};Node* newNode(int value) {
Node* node = new Node();
node->data = value;
node->left = node->right = NULL;
return node;
}

void preorder(Node* root) {
if (root == NULL) return;
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}

int main() {
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

preorder(root);
return 0;
}

#include <iostream>

using namespace std;struct Node {

int data;

Node* left;

Node* right;

};Node* newNode(int value) {

Node* node = new Node();

node->data = value;

node->left = node->right = NULL;

return node;

}

void preorder(Node* root) {

if (root == NULL) return;

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

preorder(root->left);

preorder(root->right);

}

int main() {

Node* root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);

preorder(root);

return 0;

}

Output

8️⃣ Iterative Pre-order Traversal (Using Stack)

#include <stack>

void preorderIterative(Node* root) {
if (root == NULL) return;

stack<Node*> st;
st.push(root);

while (!st.empty()) {
Node* curr = st.top();
st.pop();

cout << curr->data << " ";

// Push right first so left is processed first
if (curr->right) st.push(curr->right);
if (curr->left) st.push(curr->left);
}
}

#include <stack>

void preorderIterative(Node* root) {

if (root == NULL) return;

stack<Node*> st;

st.push(root);

while (!st.empty()) {

Node* curr = st.top();

st.pop();

cout << curr->data << " ";

// Push right first so left is processed first

if (curr->right) st.push(curr->right);

if (curr->left) st.push(curr->left);

}

9️⃣ Time & Space Complexity

Time Complexity

Space Complexity

Recursive: O(h) (height of tree)
Iterative: O(h) (stack)

🔟 Where is Pre-order Traversal Used?

✔ Copying a tree
✔ Creating expression trees
✔ Prefix expressions
✔ Serialization of trees
✔ DFS-based algorithms

1️⃣1️⃣ Pre-order vs Inorder vs Postorder

Traversal	Order
Pre-order	Root → Left → Right
Inorder	Left → Root → Right
Postorder	Left → Right → Root

Interview Questions (Pre-order)

Q1. Why root is visiting first in pre-order?
👉 That’s the definition of pre-order traversal

Q2. Can pre-order be done without recursion?
👉 Yes, using a stack

Q3. Time complexity of pre-order traversal?
👉 O(n)

Final Summary

✔ Pre-order traversal visits root first
✔ Order: Root → Left → Right
✔ Implemented using recursion or stack
✔ Time complexity: O(n)
✔ Very common in tree-based interview questions

DSA Pre-order Traversal