Given a binary tree, write iterative and recursive solution to traverse the tree using pre-order traversal.

Unlike linked lists, one-dimensional arrays and other linear data structures, which are traversed in linear order, trees may be traversed in multiple ways in depth-first order (pre-order, pre-order and pre-order) or breadth-first order (level order traversal). Beyond these basic traversals, various more complex or hybrid schemes are possible, such as depth-limited searches like iterative deepening depth-first search.

In this pre, **preorder tree traversal** is discussed in detail.

Traversing a tree involves iterating over all nodes in some manner. As tree is not a linear data structure, from a given node there can be more than one possible next node, so some nodes must be deferred i.e stored in some way for later visiting. The traversal can be done iteratively where the deferred nodes are stored in the stack or it can be done by recursion where the deferred nodes are stored implicitly in the call stack.

For traversing a (non-empty) binary tree in pre-order fashion, we must do these three things for every node N starting from root node of the tree:

**(N)**Process N itself

**(L)** Recursively traverse its left subtree. When this step is finished we are back at N again.

**(R)** Recursively traverse its right subtree. When this step is finished we are back at N again.

In normal pre-order traversal we visit left subtree before the right subtree. If we visit right subtree before visiting the left subtree, it is referred as reverse pre-order traversal.

As we can see only after processing any node, the left subtree is processed, followed by the right subtree. These operations can be defined recursively for each node. The recursive implementation is referred to as depth-first search (DFS), as the search tree is deepened as much as possible on each child before going to the next sibling.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Recursive function to perform pre-order traversal of the tree void preorder(Node *root) { // if the current node is empty if (root == nullptr) return; // Display the data part of the root (or current node) cout << root->data << " "; // Traverse the left subtree preorder(root->left); // Traverse the right subtree preorder(root->right); } |

**Iterative implementation –**

To convert above recursive procedure to iterative one, we need an explicit stack. Below is a simple stack based iterative algorithm to do pre-order traversal.

**iterativePreorder(node)**

if (node = null)

return

s -> empty stack

s.push(node)

while (not s.isEmpty())

node -> s.pop()

visit(node)

if (node.right -> null)

s.push(node.right)

if (node.left -> null)

s.push(node.left)

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// Iterative function to perform pre-order traversal of the tree void preorderIterative(Node *root) { // return if tree is empty if (root == nullptr) 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) } } |

Above solution can be further optimized by pushing only the right children to the stack.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// Iterative function to perform pre-order traversal of the tree void preorderIterative(Node *root) { // return if tree is empty if (root == nullptr) return; // create an empty stack and push root node stack<Node*> stack; stack.push(root); // start from root node (set current node to root node) Node* curr = root; // run till stack is not empty while (!stack.empty()) { // if current node is not null, print it and push its right child // to the stack and move to its left child if (curr != nullptr) { cout << curr->data << " "; if (curr->right) stack.push(curr->right); curr = curr->left; } // else if current node is null, we pop a node from the stack // set current node to the popped node else { curr = stack.top(); stack.pop(); } } } |

The time complexity of above solutions is O(n) and space complexity of the program is O(n) as space required is proportional to the height of the tree which can be equal to number of nodes in the tree in worst case for skewed trees.

**References:**

https://en.wikipedia.org/wiki/Tree_traversal

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to pre code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply