Problem Statement
Given a binary tree, return the preorder traversal of its nodes’ values.
Sample Test Cases
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3]
Problem Solution
We start traversal by pushing the root node into Stack and loop until Stack is empty. In each iteration, you pop the last element from Stack and print its value. That means you visited it. Now, push the left and right nodes into Stack if they are not null.
The order on which we push the left and right node is critical. We must first push right subtree followed by left subtree because in pre-order we visit left subtree after the node.
In the next iteration when We call pop() it will return left node because Stack is a LIFO data structure.
The exact steps of iterative pre-order traversal :
- Create an empty stack
- Push the root into Stack
- Loop until Stack is empty
- Pop the last node and print its value
- Push right and left node if they are not null
- Repeat from step 4 to 6 again.
Complexity Analysis
Time Complexity: O(N) where N is the no of Nodes in the tree. As we are visiting all the nodes once.
Space Complexity: O(N), where N is the total number of nodes in the tree. Because at any point no of nodes in the stack will be less than or equal to total no of nodes.
Code Implementation
#include <iostream>
#include <stack>
using namespace std;
// Data structure to store a Binary Tree node
class Node
{
public:
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = NULL;
}
};
// Iterative function to perform pre-order traversal of the tree
void preorderIterative(Node *root)
{
// return if tree is empty
if (root == NULL)
return;
// create an empty stack and push root node
stack<Node*> stack;
stack.push(root);
// run till stack is not empty
while (!stack.empty())
{
// pop a node from the stack and print it
Node *curr = stack.top();
stack.pop();
cout << curr->data << " ";
// push right child of popped node to the stack
if (curr->right)
stack.push(curr->right);
// push left child of popped node to the stack
if (curr->left)
stack.push(curr->left);
// important note - right child is pushed first so that left child
// is processed first (FIFO order)
}
}
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(6);
root->right->left->left = new Node(7);
root->right->left->right = new Node(8);
preorderIterative(root);
return 0;
}
