Given a binary tree, write an iterative function to print the Preorder traversal of the tree. The Preorder traversal follows the order: Root → Left → Right.
Examples:
Input:
1
/ \
2 3
/ \
4 5
Output: 1 2 4 5 3
Explanation: Preorder traversal (Root->Left->Right) of the tree is 1 2 4 5 3.Input:
8
/ \
1 5
\ / \
7 10 6
\ /
10 6
Output: 8 1 7 10 5 10 6 6
Explanation:
Preorder traversal (Root->Left->Right) of the tree is 8 1 7 10 5 10 6 6.
Try it on GfG Practice
Table of Content
[Naive Approach] Simple Iterative Preorder (with stack) - O(n) time and O(n) space
Following is a simple stack based iterative process to print Preorder traversal.
- Create an empty stack and push root node to stack.
- Do the following while is not empty.
- Pop an item from the stack and print it.
- Push right child of a popped item to stack
- Push left child of a popped item to stack
The right child is pushed before the left child to make sure that the left subtree is processed first.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int x) {
data = x;
left = right = nullptr;
}
};
vector<int> preOrder(Node* root) {
vector<int> res;
if (root == nullptr)
return res;
stack<Node*> s;
s.push(root);
while (!s.empty()) {
Node* curr = s.top();
s.pop();
res.push_back(curr->data);
if (curr->right != nullptr)
s.push(curr->right);
if (curr->left != nullptr)
s.push(curr->left);
}
return res;
}
int main() {
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);
vector<int> preorder = preOrder(root);
for (int val : preorder) {
cout << val << " ";
}
cout << endl;
return 0;
}
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
left = right = null;
}
}
public class GfG {
public static List<Integer> preOrder(Node root) {
List<Integer> res = new ArrayList<>();
if (root == null)
return res;
Stack<Node> s = new Stack<>();
s.push(root);
while (!s.isEmpty()) {
Node curr = s.pop();
res.add(curr.data);
if (curr.right != null)
s.push(curr.right);
if (curr.left != null)
s.push(curr.left);
}
return res;
}
public static void main(String[] args) {
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);
List<Integer> preorder = preOrder(root);
for (int val : preorder) {
System.out.print(val + " ");
}
System.out.println();
}
}
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def preOrder(root):
res = []
if root is None:
return res
stack = [root]
while stack:
curr = stack.pop()
res.append(curr.data)
if curr.right:
stack.append(curr.right)
if curr.left:
stack.append(curr.left)
return res
if __name__ == '__main__':
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
preorder = preOrder(root)
print(' '.join(map(str, preorder)))
using System;
using System.Collections.Generic;
class Node {
public int data;
public Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
class GfG {
public static List<int> PreOrder(Node root) {
List<int> res = new List<int>();
if (root == null)
return res;
Stack<Node> s = new Stack<Node>();
s.Push(root);
while (s.Count > 0) {
Node curr = s.Pop();
res.Add(curr.data);
if (curr.right != null)
s.Push(curr.right);
if (curr.left != null)
s.Push(curr.left);
}
return res;
}
static void Main(string[] args) {
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);
List<int> preorder = PreOrder(root);
Console.WriteLine(string.Join(" ", preorder));
}
}
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
function preOrder(root) {
const res = [];
if (root === null)
return res;
const stack = [root];
while (stack.length > 0) {
const curr = stack.pop();
res.push(curr.data);
if (curr.right)
stack.push(curr.right);
if (curr.left)
stack.push(curr.left);
}
return res;
}
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);
const preorder = preOrder(root);
console.log(preorder.join(' '));
Output
1 2 4 5 3
[Better Approach] Iterative Preorder with Current Pointer (with stack) - O(n) time and O(n) space
In the previous solution we can see that the left child is popped as soon as it is pushed to the stack, therefore it is not required to push it into the stack.
The idea is to start traversing the tree from the root node and keep printing the left child while exists and simultaneously, push the right child of every node in an auxiliary stack. Once we reach a null node, pop a right child from the auxiliary stack and repeat the process while the auxiliary stack is not empty.
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
vector<int> preOrder(Node* root)
{
vector<int> res;
if (root == NULL)
return res;
stack<Node*> s;
Node* curr = root;
while (!s.empty() || curr != NULL) {
while (curr != NULL) {
res.push_back(curr->data);
if (curr->right)
s.push(curr->right);
curr = curr->left;
}
if (!s.empty()) {
curr = s.top();
s.pop();
}
}
return res;
}
int main()
{
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);
vector<int> res = preOrder(root);
for (int x : res) {
cout << x << " ";
}
cout << endl;
return 0;
}
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
this.left = this.right = null;
}
}
public class GfG {
static List<Integer> preOrder(Node root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<Node> s = new Stack<>();
Node curr = root;
while (!s.isEmpty() || curr != null) {
while (curr != null) {
res.add(curr.data);
if (curr.right != null) s.push(curr.right);
curr = curr.left;
}
if (!s.isEmpty()) {
curr = s.pop();
}
}
return res;
}
public static void main(String[] args) {
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);
List<Integer> res = preOrder(root);
for (int x : res) {
System.out.print(x + " ");
}
System.out.println();
}
}
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def preOrder(root):
res = []
if root is None:
return res
stack = []
curr = root
while stack or curr:
while curr:
res.append(curr.data)
if curr.right:
stack.append(curr.right)
curr = curr.left
if stack:
curr = stack.pop()
return res
if __name__ == '__main__':
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
res = preOrder(root)
print(' '.join(map(str, res)))
using System;
using System.Collections.Generic;
using System.Collections;
class Node {
public int data;
public Node left, right;
public Node(int data) {
this.data = data;
this.left = this.right = null;
}
}
public class GfG {
static List<int> PreOrder(Node root) {
List<int> res = new List<int>();
if (root == null) return res;
Stack<Node> s = new Stack<Node>();
Node curr = root;
while (s.Count > 0 || curr != null) {
while (curr != null) {
res.Add(curr.data);
if (curr.right != null) s.Push(curr.right);
curr = curr.left;
}
if (s.Count > 0) {
curr = s.Pop();
}
}
return res;
}
public static void Main(string[] args) {
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);
List<int> res = PreOrder(root);
foreach (int x in res) {
Console.Write(x + " ");
}
Console.WriteLine();
}
}
// Node structure
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
function preOrder(root) {
const res = [];
if (root === null) return res;
const s = [];
let curr = root;
while (s.length > 0 || curr !== null) {
while (curr !== null) {
res.push(curr.data);
if (curr.right) s.push(curr.right);
curr = curr.left;
}
if (s.length > 0) {
curr = s.pop();
}
}
return res;
}
// Example usage
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);
const res = preOrder(root);
console.log(res.join(' '));
Output
1 2 4 5 3
[Expected Approach] Preorder Morris Traversal - O(n) time and O(1) space
Morris Traversal is a tree traversal technique that allows you to traverse a binary tree without using recursion or a stack. The Preorder Morris Traversal algorithm works by manipulating the tree's pointers, specifically by utilizing the inorder predecessor of each node.
Algorithm for Preorder Morris Traversal:
1. If the left child of the current node is NULL:
- Print the current node's data (since it is the root of the subtree).
- Move to the right child of the current node.
2. If the left child of the current node is NOT NULL:
- Find the inorder predecessor of the current node: The inorder predecessor is the rightmost node of the left subtree of the current node.
Two cases arise:
a) The right child of the inorder predecessor already points to the current node:
- This means we've already visited this node, so we can set the right child of the inorder predecessor to NULL.
- Move to the right child of the current node.
b) The right child of the inorder predecessor is NULL:
- Set the right child of the inorder predecessor to point to the current node.
- Print the current node's data.
- Move to the left child of the current node (this is the new node to visit next).
3. Repeat the process until the current node is NULL.
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int item) {
data = item;
left = right = nullptr;
}
};
vector<int> morrisPreOrder(Node* node) {
vector<int> res;
while (node != nullptr) {
if (node->left == nullptr) {
res.push_back(node->data);
node = node->right;
} else {
Node* curr = node->left;
while (curr->right != nullptr && curr->right != node) {
curr = curr->right;
}
if (curr->right == node) {
curr->right = nullptr;
node = node->right;
} else {
res.push_back(node->data);
curr->right = node;
node = node->left;
}
}
}
return res;
}
int main() {
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);
vector<int> res = morrisPreOrder(root);
for (int value : res) {
cout << value << " ";
}
cout << endl;
return 0;
}
import java.util.ArrayList;
import java.util.List;
class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
public class MorrisPreorder {
public static List<Integer> morrisPreOrder(Node node) {
List<Integer> result = new ArrayList<>();
while (node != null) {
if (node.left == null) {
result.add(node.data);
node = node.right;
} else {
Node current = node.left;
while (current.right != null && current.right != node) {
current = current.right;
}
if (current.right == node) {
current.right = null;
node = node.right;
} else {
result.add(node.data);
current.right = node;
node = node.left;
}
}
}
return result;
}
public static void main(String[] args) {
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);
List<Integer> morrisResult = morrisPreOrder(root);
for (int value : morrisResult) {
System.out.print(value + " ");
}
System.out.println();
}
}
class Node:
def __init__(self, item):
self.data = item
self.left = None
self.right = None
def morrisPreorder(node):
result = []
while node:
if node.left is None:
result.append(node.data)
node = node.right
else:
current = node.left
while current.right and current.right != node:
current = current.right
if current.right == node:
current.right = None
node = node.right
else:
result.append(node.data)
current.right = node
node = node.left
return result
if __name__ == '__main__':
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
morris_result = morrisPreorder(root)
print(' '.join(map(str, morris_result)))
using System;
using System.Collections.Generic;
class Node {
public int data;
public Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class MorrisPreorder {
public static List<int> MorrisPreOrder(Node node) {
List<int> result = new List<int>();
while (node != null) {
if (node.left == null) {
result.Add(node.data);
node = node.right;
} else {
Node current = node.left;
while (current.right != null && current.right != node) {
current = current.right;
}
if (current.right == node) {
current.right = null;
node = node.right;
} else {
result.Add(node.data);
current.right = node;
node = node.left;
}
}
}
return result;
}
public static void Main() {
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);
List<int> morrisResult = MorrisPreOrder(root);
foreach (int value in morrisResult) {
Console.Write(value + " ");
}
Console.WriteLine();
}
}
class Node {
constructor(item) {
this.data = item;
this.left = null;
this.right = null;
}
}
function morrisPreOrder(node) {
const result = [];
while (node) {
if (node.left === null) {
result.push(node.data);
node = node.right;
} else {
let current = node.left;
while (current.right !== null && current.right !== node) {
current = current.right;
}
if (current.right === node) {
current.right = null;
node = node.right;
} else {
result.push(node.data);
current.right = node;
node = node.left;
}
}
}
return result;
}
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);
const morrisResult = morrisPreOrder(root);
console.log(morrisResult.join(' '));
Output
1 2 4 5 3
Refer Preorder Traversal of Binary Tree for recursive code