Pre-order binary tree traversal is a technique used to visit all the nodes of a binary tree in the following order: First, the root node of the current tree is visited, then all nodes in the left subtree are visited in pre-order fashion, and finally all the nodes in the right subtree are visited in pre-order fashion. The animated examples discussed in the next section will make the definition more clear.
Animation of Pre-Order Binary Tree Traversal
Let’s consider the below binary tree and apply the pre-order tree traversal technique:
Node A is the root node of the binary tree. We need to visit this node before visiting all the nodes under it’s left and right subtrees in pre-order fashion. Visited nodes will be coloured in green.
Now we need to visit all the nodes under the left subtree of node A i.e., subtree with root as node B in pre-order fashion. We apply the same logic again i.e, first visit the subtree’s root node (B), then visit all nodes in left subtree under node B, and then visit all nodes in right subtree under node B. So we visit node B, left subtree of node B contains a singe node D so we just visit that node and finally visit node E.
Now that all the nodes under the left subtree of node A are visited, we need to visit all nodes under the right subtree of node A in pre-order fashion.
This is the order in which we visited all the nodes: A, B, D, E, C, F, G.
Recursive Implementation
Below is the implementation of a function which takes in the root node of a binary tree and traverses all the nodes in Pre-Order fashion. It uses recursion technique which is much simpler and straightforward than the iterative version.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def pre_order_traversal(node):
# Base case: if the node is None, return
if node is None:
return
# Step 1: Visit the current node
# print its value or perform any other operation
print(node.value, end=" ")
# Step 2: Traverse the left subtree recursively
pre_order_traversal(node.left)
# Step 3: Traverse the right subtree recursively
pre_order_traversal(node.right)
# Create a sample binary tree
def create_binary_tree():
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
return root
# Let's now test the pre_order_traversal function
if __name__ == "__main__":
tree_root = create_binary_tree()
print("Pre-Order Traversal:")
pre_order_traversal(tree_root)
#include <stdio.h>
#include <stdlib.h>
// Node structure to represent a binary tree node
typedef struct Node {
int value;
struct Node* left;
struct Node* right;
} Node;
// Function to create a new node with the given value
Node* create_node(int value) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->value = value;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
// Function to perform pre-order traversal
void pre_order_traversal(Node* node) {
// Base case: if the node is NULL, return
if (node == NULL) {
return;
}
// Step 1: Visit the current node
// Print its value or perform any other operation
printf("%d ", node->value);
// Step 2: Traverse the left subtree recursively
pre_order_traversal(node->left);
// Step 3: Traverse the right subtree recursively
pre_order_traversal(node->right);
}
// Function to create a sample binary tree
Node* create_binary_tree() {
Node* root = create_node(1);
root->left = create_node(2);
root->right = create_node(3);
root->left->left = create_node(4);
root->left->right = create_node(5);
root->right->left = create_node(6);
root->right->right = create_node(7);
return root;
}
int main() {
Node* tree_root = create_binary_tree();
printf("Pre-Order Traversal:\n");
pre_order_traversal(tree_root);
printf("\n");
// Ideally you need to clean up all created nodes
// to avoid memory leaks
return 0;
}
#include <iostream>
// Node class to represent a node in the binary tree
class Node {
public:
int value;
Node* left;
Node* right;
// Constructor to initialize the node
Node(int val) {
value = val;
left = nullptr;
right = nullptr;
}
};
// Function to perform pre-order traversal
void pre_order_traversal(Node* node) {
// Base case: if the node is nullptr, return
if (node == nullptr) {
return;
}
// Step 1: Visit the current node
// print its value or perform any other operation
std::cout << node->value << " ";
// Step 2: Traverse the left subtree recursively
pre_order_traversal(node->left);
// Step 3: Traverse the right subtree recursively
pre_order_traversal(node->right);
}
// Function to create a sample binary tree
Node* create_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);
root->right->left = new Node(6);
root->right->right = new Node(7);
return root;
}
int main() {
// Create the binary tree
Node* tree_root = create_binary_tree();
// Perform pre-order traversal
std::cout << "Pre-Order Traversal:" << std::endl;
pre_order_traversal(tree_root);
std::cout << std::endl;
// Ideally you need to clean up all created nodes
// to avoid memory leaks
return 0;
}
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function preOrderTraversal(node) {
// Base case: if the node is null, return
if (node === null) {
return;
}
// Step 1: Visit the current node
// print its value or perform any other operation
console.log(node.value, " ");
// Step 2: Traverse the left subtree recursively
preOrderTraversal(node.left);
// Step 3: Traverse the right subtree recursively
preOrderTraversal(node.right);
}
// Create a sample binary tree
function createBinaryTree() {
const 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);
root.right.left = new Node(6);
root.right.right = new Node(7);
return root;
}
// Let's now test the preOrderTraversal function
const treeRoot = createBinaryTree();
console.log("Pre-Order Traversal:");
preOrderTraversal(treeRoot);
class Node {
int value;
Node left;
Node right;
Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
public class Main {
// Pre-order traversal function
static void preOrderTraversal(Node node) {
// Base case: if the node is null, return
if (node == null) {
return;
}
// Step 1: Visit the current node
// print its value or perform any other operation
System.out.print(node.value + " ");
// Step 2: Traverse the left subtree recursively
preOrderTraversal(node.left);
// Step 3: Traverse the right subtree recursively
preOrderTraversal(node.right);
}
// Create a sample binary tree
static Node createBinaryTree() {
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);
root.right.left = new Node(6);
root.right.right = new Node(7);
return root;
}
public static void main(String[] args) {
Node treeRoot = createBinaryTree();
System.out.println("Pre-Order Traversal:");
preOrderTraversal(treeRoot);
}
}
Iterative Implementation
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def iterative_pre_order_traversal(root):
if root is None:
return
# Initialize a stack to simulate recursion
stack = [root]
# Traverse the tree until the stack is empty
while stack:
# Pop the top node from the stack
node = stack.pop()
# Visit the node (print or perform any operation)
print(node.value, end=" ")
# Push the right child to the stack first
if node.right:
stack.append(node.right)
# Push the left child to the stack
# Since the stack is LIFO, the left child will be visited before the right child
if node.left:
stack.append(node.left)
# Create a sample binary tree
def create_binary_tree():
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
return root
# Iterative pre-order traversal usage
if __name__ == "__main__":
tree_root = create_binary_tree()
print("Iterative Pre-Order Traversal:")
iterative_pre_order_traversal(tree_root)
#include <iostream>
#include <stack>
// Node class to represent a node in the binary tree
class Node {
public:
int value;
Node* left;
Node* right;
// Constructor to initialize a node
Node(int val) {
value = val;
left = nullptr;
right = nullptr;
}
};
// Function to perform iterative pre-order traversal
void iterative_pre_order_traversal(Node* root) {
// Check if the root is null
if (root == nullptr) {
return;
}
// Initialize a stack to simulate recursion
std::stack<Node*> stack;
stack.push(root);
// Traverse the tree until the stack is empty
while (!stack.empty()) {
// Pop the top node from the stack
Node* node = stack.top();
stack.pop();
// Visit the node (print or perform any operation)
std::cout << node->value << " ";
// Push the right child to the stack first
if (node->right) {
stack.push(node->right);
}
// Push the left child to the stack
// Since the stack is LIFO, the left child will be visited before the right child
if (node->left) {
stack.push(node->left);
}
}
}
// Function to create a sample binary tree
Node* create_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);
root->right->left = new Node(6);
root->right->right = new Node(7);
return root;
}
int main() {
// Create a sample binary tree
Node* tree_root = create_binary_tree();
// Perform iterative pre-order traversal
std::cout << "Iterative Pre-Order Traversal:" << std::endl;
iterative_pre_order_traversal(tree_root);
std::cout << std::endl;
// Ideally you need to clean up all created nodes
// to avoid memory leaks
return 0;
}
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function iterativePreOrderTraversal(root) {
// Check if the root is null
if (root === null) {
return;
}
// Initialize a stack to simulate recursion
let stack = [root];
// Traverse the tree until the stack is empty
while (stack.length > 0) {
// Pop the top node from the stack
let node = stack.pop();
// Visit the node (print or perform any operation)
console.log(node.value, " ");
// Push the right child to the stack first
if (node.right) {
stack.push(node.right);
}
// Push the left child to the stack
// Since the stack is LIFO, the left child will be visited before the right child
if (node.left) {
stack.push(node.left);
}
}
}
// Create a sample binary tree
function createBinaryTree() {
let 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);
root.right.left = new Node(6);
root.right.right = new Node(7);
return root;
}
// Iterative pre-order traversal usage
if (require.main === module) {
let treeRoot = createBinaryTree();
console.log("Iterative Pre-Order Traversal:");
iterativePreOrderTraversal(treeRoot);
}
import java.util.Stack;
public class Main {
// Node class to represent a node in the binary tree
static class Node {
int value;
Node left;
Node right;
Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Iterative pre-order traversal of the binary tree
static void iterativePreOrderTraversal(Node root) {
// Check if the root is null
if (root == null) {
return;
}
// Initialize a stack to simulate recursion
Stack<Node> stack = new Stack<>();
stack.push(root);
// Traverse the tree until the stack is empty
while (!stack.isEmpty()) {
// Pop the top node from the stack
Node node = stack.pop();
// Visit the node (print or perform any operation)
System.out.print(node.value + " ");
// Push the right child to the stack first
if (node.right != null) {
stack.push(node.right);
}
// Push the left child to the stack
// Since the stack is LIFO, the left child will be visited before the right child
if (node.left != null) {
stack.push(node.left);
}
}
}
// Create a sample binary tree
static Node createBinaryTree() {
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);
root.right.left = new Node(6);
root.right.right = new Node(7);
return root;
}
public static void main(String[] args) {
Node treeRoot = createBinaryTree();
System.out.println("Iterative Pre-Order Traversal:");
iterativePreOrderTraversal(treeRoot);
}
}