13,353,322 members (52,893 online)
Tip/Trick
alternative version

#### Stats

31.2K views
6 bookmarked
Posted 9 Feb 2014

# Depth First Search (DFS) Non-recursive

, 9 Feb 2014
 Rate this:
DFS algorithm to print the element of a Binary Search Tree in order in which just by traversing with a DFS algorithm is possible

## Introduction

A friend asked me about an interview question, how to write a non-recursive DFS algorithm for traversing a binary tree. So I decided to share it with you here.

## Background

In the following code, I apply the DFS algorithm to print the element of a Binary Search Tree in order in which just by traversing with a DFS algorithm is possible.

## Using the Code

The logic of the algorithm is traverse to left subtrees as much as possible and push them into the stack. When reaching the end, you pop one element from the stack and print it.Then for the node that is popped from the stack again, we should do the same thing (find the left elements) on the right subtree of that node, and we continue until the stack becomes empty.

```#include <stack>
struct BTNode
{

BTNode(int d)
{
data = d;
}

int data;
BTNode* right;
BTNode* left;
};

void DFS(BTNode* root)
{
BTNode* tmp = root;
std::stack<BTNode*> stck;
stck.push(tmp);

//Until the stack is not empty, it means there are nodes to traverse
while(stck.empty() == false)
{
while (tmp->left != 0)
{
tmp = tmp->left;
stck.push(tmp);
}
while(stck.empty() == false)
{
tmp = stck.top();
stck.pop();
std::cout << tmp->data;
if(tmp->right != 0)
{
tmp = tmp->right;
stck.push(tmp);
break;
}
}
}

void CreateTreeExample(BTNode* root)
{
BTNode* b1= new BTNode(1);
BTNode* b2= new BTNode(2);
BTNode* b3= new BTNode(3);
BTNode* b4= new BTNode(4);
BTNode* b5= new BTNode(5);
BTNode* b6= new BTNode(6);
BTNode* b7= new BTNode(7);
BTNode* b8= new BTNode(8);
BTNode* b9= new BTNode(9);

b2->left = b1;
b2->right = b4;
b6->left = b2;
b4->left = b3;
b4->right = b5;
b7->left = b6;
b7->right = b8;
b8->right = b9;
root = b7;
} ```

To test the algorithm, make a simple binary tree by calling the method:
// 7
// / \
// 6 8
// / \
// 2 9
// / \
// 1 4
// / \
// 3 5

```BTNode* root;
CreateTreeExample(root) ;  ```

and call the DFS method. The output for the example binary tree is:

1
2
3
4
5
6
7
8
9

## Points of Interest

FYI, you can use the same concept to solve the question:

Given a binary tree, write a program to convert it to a doubly linked list. The nodes in the doubly linked list are arranged in a sequence formed by a zig-zag level order traversal.

## About the Author

No Biography provided

## Comments and Discussions

 First Prev Next
 My vote of 2 Andreas Gieriet24-Jan-15 21:42 Andreas Gieriet 24-Jan-15 21:42
 Idiomatic C++ would demand for input iterators (prefix/infix/postfix) Andreas Gieriet20-Jan-15 15:39 Andreas Gieriet 20-Jan-15 15:39
 Re: Idiomatic C++ would demand for input iterators (prefix/infix/postfix) Shiva Varshovi_21-Jan-15 16:42 Shiva Varshovi_ 21-Jan-15 16:42
 Re: Idiomatic C++ would demand for input iterators (prefix/infix/postfix) Andreas Gieriet24-Jan-15 21:40 Andreas Gieriet 24-Jan-15 21:40
 My vote of 1 sdcp20-Oct-14 9:35 sdcp 20-Oct-14 9:35
 while( true) charlie10027-Jul-14 17:14 charlie100 27-Jul-14 17:14
 Re: while( true) sdcp20-Oct-14 9:36 sdcp 20-Oct-14 9:36
 Re: while( true) Shiva Varshovi_20-Jan-15 14:11 Shiva Varshovi_ 20-Jan-15 14:11
 Next challenge YvesDaoust10-Feb-14 1:06 YvesDaoust 10-Feb-14 1:06
 Re: Next challenge Shiva Varshovi_12-Feb-14 16:11 Shiva Varshovi_ 12-Feb-14 16:11
 Last Visit: 31-Dec-99 19:00     Last Update: 21-Jan-18 14:52 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.