Preorder Without Recursion
This is an implementation of a binary tree in C++ with various operations, including the preorder traversal algorithm implemented iteratively (without recursion):The algorithm follows these steps:
- 1. Create an empty stack and push the root node onto the stack.
-
2. While the stack is not empty, do the following:
- Pop a node from the stack and print its data.
- Push the right child of the popped node onto the stack (if it exists).
- Push the le child of the popped node onto the stack (if it exists).br - 3. Repeat steps 2 until the stack is empty.
#include <iostream>
#include <stack>
// Node structure for the binary tree
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
// Function to insert a new node into the binary tree
void insertNode(Node*& root, int value) {
if (root == nullptr) {
root = new Node(value);
return;
}
std::queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* curr = q.front();
q.pop();
if (curr->left == nullptr) {
curr->left = new Node(value);
return;
} else {
q.push(curr->left);
}
if (curr->right == nullptr) {
curr->right = new Node(value);
return;
} else {
q.push(curr->right);
}
}
}
// Function to perform preorder traversal iteratively (without recursion)
void preorderTraversal(Node* root) {
if (root == nullptr) {
return;
}
std::stack<Node*> stk;
stk.push(root);
while (!stk.empty()) {
Node* curr = stk.top();
stk.pop();
std::cout << curr->data << " ";
if (curr->right != nullptr) {
stk.push(curr->right);
}
if (curr->left != nullptr) {
stk.push(curr->left);
}
}
}
int main() {
Node* root = nullptr;
// Insert nodes into the binary tree
insertNode(root, 1);
insertNode(root, 2);
insertNode(root, 3);
insertNode(root, 4);
insertNode(root, 5);
// Perform preorder traversal
std::cout << "Preorder Traversal: ";
preorderTraversal(root); // Output: 1 2 4 5 3
std::cout << std::endl;
// Clean up memory (optional)
// ...
return 0;
}
- In this implementaon, we have a Node structure that represents a node in the binary tree. Each node contains a data value and pointers to its le and right child nodes.
- The insertNode funcon is used to insert a new node into the binary tree. It follows a level order traversal approach using a queue to find the appropriate posion to insert the node.
-
The preorderTraversal funcon performs a preorder traversal of the binary tree iteravely,
without using recursion. It u lizes a stack to keep track of nodes to be visited. The algorithm
follows these steps:
- 1. Create an empty stack and push the root node onto the stack.
-
2. While the stack is not empty, do the following:
- Pop a node from the stack and print its data.
- Push the right child of the popped node onto the stack (if it exists).
- Push the le child of the popped node onto the stack (if it exists).br - 3. Repeat steps 2 until the stack is empty.
In the main funcon, we create a binary tree by inserng nodes with values 1, 2, 3, 4, and
5. We then perform the preorder traversal to print the data of the nodes in the tree.
Preorder traversal: 1 2 3 4 5
With Recursion
This is an example implementation of a binary tree in C++ along with the preorder traversal algorithm:
#include <iostream>
// Binary tree node structure
struct Node {
int data;
Node* left;
Node* right;
};
// Function to create a new node
Node* createNode(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->left = nullptr;
newNode->right = nullptr;
return newNode;
}
// Function to insert a node in the binary tree
void insertNode(Node* root, int value) {
if (root == nullptr) {
root = createNode(value);
return;
}
if (value < root->data) {
if (root->left == nullptr) {
root->left = createNode(value);
} else {
insertNode(root->left, value);
}
} else {
if (root->right == nullptr) {
root->right = createNode(value);
} else {
insertNode(root->right, value);
}
}
}
// Preorder traversal algorithm explanation:
// Preorder traversal visits the root node, then the left subtree, and finally the right subtree.
// Algorithm steps:
// 1. Visit the root node.
// 2. Traverse the left subtree recursively using preorder traversal.
// 3. Traverse the right subtree recursively using preorder traversal.
// Preorder traversal using recursion
void preorderTraversal(Node* root) {
if (root == nullptr) {
return;
}
// 1. Visit the root node
std::cout << root->data << " ";
// 2. Traverse the left subtree recursively
preorderTraversal(root->left);
// 3. Traverse the right subtree recursively
preorderTraversal(root->right);
}
int main() {
// Create the binary tree
Node* root = createNode(4);
insertNode(root, 2);
insertNode(root, 6);
insertNode(root, 1);
insertNode(root, 3);
insertNode(root, 5);
insertNode(root, 7);
// Perform preorder traversal
std::cout << "Preorder traversal: ";
preorderTraversal(root); // Output: 4 2 1 3 6 5 7
std::cout << std::endl;
return 0;
}
- In this implementaon, we have a Node structure that represents a node in the binary tree. Each node contains an integer data value, and two pointers to its le child and right child.
- The createNode funcon is used to create a new node with the given value. The insertNode funcon is used to insert a node in the binary tree based on the node's value. The funcon recursively searches for the appropriate posion to insert the new node, following the binary search tree property.
- The preorderTraversal funcon performs the preorder traversal of the binary tree. It takes a node as input and follows the steps of the preorder traversal algorithm: vising the root node, traversing the le subtree recursively, and traversing the right subtree recursively. The funcon prints the data value of each visited node.
- In the main funcon, we create a binary tree and insert nodes with different values. Then we perform the preorder traversal by calling the preorderTraversal funcon and print the output.
Preorder traversal: 4 2 1 3 6 5 7