Given a binary tree, write a program to perform an iterative in-order traversal and print the values of the nodes as they are visited.
Consider the following binary tree:
1
/ \
2 3
/ \
4 5
Expected Output:
The expected output for the in-order traversal of the given binary tree is: 2 1 4 3 5.
Table of Contents
C++ Solution:
#include <iostream>
#include <stack>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// Function to perform iterative in-order traversal
void iterativeInOrderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* current = root;
while (current || !st.empty()) {
// Traverse to the leftmost node while pushing nodes onto the stack
while (current) {
st.push(current);
current = current->left;
}
// Pop a node, visit it, and move to its right subtree
current = st.top();
st.pop();
cout << current->val << " ";
current = current->right;
}
}
int main() {
// Create the binary tree
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->right->left = new TreeNode(4);
root->right->right = new TreeNode(5);
// Perform iterative in-order traversal
cout << "Iterative In-order Traversal: ";
iterativeInOrderTraversal(root);
cout << endl;
return 0;
}
Time and Space Complexity:
The time complexity of the iterative in-order traversal is O(n), where n is the number of nodes in the binary tree, since we visit each node once.
The space complexity is O(h), where h is the height of the binary tree.
In the worst case (skewed tree), the space complexity could be O(n), and in the best case (balanced tree), it could be O(log n).
In this program, the iterativeInOrderTraversal function performs the iterative in-order traversal using a stack to keep track of the nodes. It starts by traversing to the leftmost node while pushing nodes onto the stack. Then, it pops a node, visits it, and moves to its right subtree. This process continues until all nodes are visited.
The main function creates a binary tree, calls the iterativeInOrderTraversal function, and prints the in-order traversal of the tree.