Click here to Skip to main content
12,077,911 members (47,925 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

20.6K views
6 bookmarked
Posted

Depth First Search (DFS) Non-recursive

, 9 Feb 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Shiva Varshovi_
Software Developer
Canada Canada
No Biography provided

You may also be interested in...

Comments and Discussions

 
GeneralMy vote of 2 Pin
Andreas Gieriet24-Jan-15 21:42
professionalAndreas Gieriet24-Jan-15 21:42 
QuestionIdiomatic C++ would demand for input iterators (prefix/infix/postfix) Pin
Andreas Gieriet20-Jan-15 15:39
professionalAndreas Gieriet20-Jan-15 15:39 
AnswerRe: Idiomatic C++ would demand for input iterators (prefix/infix/postfix) Pin
Shiva Varshovi_21-Jan-15 16:42
memberShiva Varshovi_21-Jan-15 16:42 
GeneralRe: Idiomatic C++ would demand for input iterators (prefix/infix/postfix) Pin
Andreas Gieriet24-Jan-15 21:40
professionalAndreas Gieriet24-Jan-15 21:40 
GeneralMy vote of 1 Pin
sdcp20-Oct-14 9:35
membersdcp20-Oct-14 9:35 
Questionwhile( true) Pin
charlie10027-Jul-14 17:14
membercharlie10027-Jul-14 17:14 
AnswerRe: while( true) Pin
sdcp20-Oct-14 9:36
membersdcp20-Oct-14 9:36 
GeneralRe: while( true) Pin
Shiva Varshovi_20-Jan-15 14:11
memberShiva Varshovi_20-Jan-15 14:11 
QuestionNext challenge Pin
YvesDaoust10-Feb-14 1:06
memberYvesDaoust10-Feb-14 1:06 
AnswerRe: Next challenge Pin
Shiva Varshovi_12-Feb-14 16:11
memberShiva Varshovi_12-Feb-14 16:11 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.160212.1 | Last Updated 9 Feb 2014
Article Copyright 2014 by Shiva Varshovi_
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid