Iterative Depth First Traversal of Graph

Last Updated : 29 Dec, 2022

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal (DFS) of a tree. The only catch here is, unlike trees, graphs may contain cycles, so a node might be visited twice. To avoid processing a node more than once, use a boolean visited array.

Example:

Input: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Output: DFS from vertex 1 : 1 2 0 3
Explanation:
DFS Diagram:

Input: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Output: DFS from vertex 2 : 2 0 1 3
Explanation:
DFS Diagram:

The recursive implementation of DFS is already discussed: previous post.
Solution:

Approach: Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. Finally print the nodes in the path.
The only difference between iterative DFS and recursive DFS is that the recursive stack is replaced by a stack of nodes.
Algorithm:
1. Created a stack of nodes and visited array.
2. Insert the root in the stack.
3. Run a loop till the stack is not empty.
4. Pop the element from the stack and print the element.
5. For every adjacent and unvisited node of current node, mark the node and insert it in the stack.
Implementation of Iterative DFS: This is similar to BFS, the only difference is queue is replaced by stack.

C++

// An Iterative C++ program to do DFS traversal from
// a given source vertex. DFS(int s) traverses vertices
// reachable from s.
#include<bits/stdc++.h>
using namespace std;
 
// This class represents a directed graph using adjacency
// list representation
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // adjacency lists
public:
    Graph(int V);  // Constructor
    void addEdge(int v, int w); // to add an edge to graph
    void DFS(int s);  // prints all vertices in DFS manner
    // from a given source.
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}
 
// prints all not yet visited vertices reachable from s
void Graph::DFS(int s)
{
    // Initially mark all vertices as not visited
    vector<bool> visited(V, false);
 
    // Create a stack for DFS
    stack<int> stack;
 
    // Push the current source node.
    stack.push(s);
 
    while (!stack.empty())
    {
        // Pop a vertex from stack and print it
        int s = stack.top();
        stack.pop();
 
        // Stack may contain same vertex twice. So
        // we need to print the popped item only
        // if it is not visited.
        if (!visited[s])
        {
            cout << s << " ";
            visited[s] = true;
        }
 
        // Get all adjacent vertices of the popped vertex s
        // If a adjacent has not been visited, then push it
        // to the stack.
        for (auto i = adj[s].begin(); i != adj[s].end(); ++i)
            if (!visited[*i])
                stack.push(*i);
    }
}
 
// Driver program to test methods of graph class
int main()
{
    Graph g(5); // Total 5 vertices in graph
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 1);
    g.addEdge(0, 3);
    g.addEdge(1, 4);
 
    cout << "Following is Depth First Traversal\n";
    g.DFS(0);
 
    return 0;
}

Java

//An Iterative Java program to do DFS traversal from
//a given source vertex. DFS(int s) traverses vertices
//reachable from s.
 
import java.util.*;
 
public class GFG 
{
    // This class represents a directed graph using adjacency
    // list representation
    static class Graph
    {
        int V; //Number of Vertices
         
        LinkedList<Integer>[] adj; // adjacency lists
         
        //Constructor
        Graph(int V)
        {
            this.V = V;
            adj = new LinkedList[V];
             
            for (int i = 0; i < adj.length; i++)
                adj[i] = new LinkedList<Integer>();
             
        }
         
        //To add an edge to graph
        void addEdge(int v, int w)
        {
            adj[v].add(w); // Add w to v’s list.
        }
         
        // prints all not yet visited vertices reachable from s
        void DFS(int s)
        {
            // Initially mark all vertices as not visited
            Vector<Boolean> visited = new Vector<Boolean>(V);
            for (int i = 0; i < V; i++)
                visited.add(false);
     
            // Create a stack for DFS
            Stack<Integer> stack = new Stack<>();
             
            // Push the current source node
            stack.push(s);
             
            while(stack.empty() == false)
            {
                // Pop a vertex from stack and print it
                s = stack.peek();
                stack.pop();
                 
                // Stack may contain same vertex twice. So
                // we need to print the popped item only
                // if it is not visited.
                if(visited.get(s) == false)
                {
                    System.out.print(s + " ");
                    visited.set(s, true);
                }
                 
                // Get all adjacent vertices of the popped vertex s
                // If a adjacent has not been visited, then push it
                // to the stack.
                Iterator<Integer> itr = adj[s].iterator();
                 
                while (itr.hasNext()) 
                {
                    int v = itr.next();
                    if(!visited.get(v))
                        stack.push(v);
                }
                 
            }
        }
    }
     
    // Driver program to test methods of graph class
    public static void main(String[] args) 
    {
        // Total 5 vertices in graph
        Graph g = new Graph(5);
         
        g.addEdge(1, 0);
        g.addEdge(0, 2);
        g.addEdge(2, 1);
        g.addEdge(0, 3);
        g.addEdge(1, 4);
             
        System.out.println("Following is the Depth First Traversal");
        g.DFS(0);
    }
}

Python3

# An Iterative Python program to do DFS traversal from 
# a given source vertex. DFS(int s) traverses vertices 
# reachable from s. 
 
# This class represents a directed graph using adjacency 
# list representation 
class Graph: 
    def __init__(self,V): # Constructor 
        self.V = V        # No. of vertices 
        self.adj  = [[] for i in range(V)]  # adjacency lists 
 
    def addEdge(self,v, w):     # to add an edge to graph
        self.adj[v].append(w)    # Add w to v’s list. 
 
 
    # prints all not yet visited vertices reachable from s 
    def DFS(self,s):            # prints all vertices in DFS manner from a given source.
                                # Initially mark all vertices as not visited 
        visited = [False for i in range(self.V)] 
 
        # Create a stack for DFS 
        stack = []
 
        # Push the current source node. 
        stack.append(s) 
 
        while (len(stack)): 
            # Pop a vertex from stack and print it 
            s = stack[-1] 
            stack.pop()
 
            # Stack may contain same vertex twice. So 
            # we need to print the popped item only 
            # if it is not visited. 
            if (not visited[s]): 
                print(s,end=' ')
                visited[s] = True
 
            # Get all adjacent vertices of the popped vertex s 
            # If a adjacent has not been visited, then push it 
            # to the stack. 
            for node in self.adj[s]: 
                if (not visited[node]): 
                    stack.append(node) 
 
 
 
# Driver program to test methods of graph class 
 
g = Graph(5); # Total 5 vertices in graph 
g.addEdge(1, 0); 
g.addEdge(0, 2); 
g.addEdge(2, 1); 
g.addEdge(0, 3); 
g.addEdge(1, 4); 
 
print("Following is Depth First Traversal") 
g.DFS(0)
 
# This code is contributed by ankush_953

C#

// An Iterative C# program to do DFS traversal from
// a given source vertex. DFS(int s) traverses vertices
// reachable from s.
using System; 
using System.Collections.Generic;
 
class GFG 
{
    // This class represents a directed graph using adjacency
    // list representation
    public class Graph
    {
        public int V; // Number of Vertices
         
        public LinkedList<int>[] adj; // adjacency lists
         
        // Constructor
        public Graph(int V)
        {
            this.V = V;
            adj = new LinkedList<int>[V];
             
            for (int i = 0; i < adj.Length; i++)
                adj[i] = new LinkedList<int>();
             
        }
         
        // To add an edge to graph
        public void addEdge(int v, int w)
        {
            adj[v].AddLast(w); // Add w to v’s list.
        }
         
        // prints all not yet visited vertices reachable from s
        public void DFS(int s)
        {
            // Initially mark all vertices as not visited
            Boolean []visited = new Boolean[V];
                 
            // Create a stack for DFS
            Stack<int> stack = new Stack<int>();
             
            // Push the current source node
            stack.Push(s);
             
            while(stack.Count > 0)
            {
                // Pop a vertex from stack and print it
                s = stack.Peek();
                stack.Pop();
                 
                // Stack may contain same vertex twice. So
                // we need to print the popped item only
                // if it is not visited.
                if(visited[s] == false)
                {
                    Console.Write(s + " ");
                    visited[s] = true;
                }
                 
                // Get all adjacent vertices of the popped vertex s
                // If a adjacent has not been visited, then push it
                // to the stack.
                foreach(int v in adj[s])
                {
                    if(!visited[v])
                        stack.Push(v);
                }
                 
            }
        }
    }
     
    // Driver code
    public static void Main(String []args) 
    {
        // Total 5 vertices in graph
        Graph g = new Graph(5);
         
        g.addEdge(1, 0);
        g.addEdge(0, 2);
        g.addEdge(2, 1);
        g.addEdge(0, 3);
        g.addEdge(1, 4);
             
        Console.Write("Following is the Depth First Traversal\n");
        g.DFS(0);
    }
}
 
// This code is contributed by Arnasb Kundu

Javascript

<script>
 
// An Iterative Javascript program to 
// do DFS traversal from a given source
// vertex. DFS(int s) traverses vertices
// reachable from s.
 
// This class represents a directed graph
// using adjacency list representation
class Graph{
     
constructor(V)
{
    this.V = V;
    this.adj = new Array(V);
     
    for(let i = 0; i < this.adj.length; i++)
        this.adj[i] = [];
}
 
// To add an edge to graph
addEdge(v, w)
{
     
    // Add w to v’s list.
    this.adj[v].push(w); 
}
 
// Prints all not yet visited 
// vertices reachable from s
DFS(s)
{
     
    // Initially mark all vertices as not visited
    let visited = [];
    for(let i = 0; i < this.V; i++)
        visited.push(false);
 
    // Create a stack for DFS
    let stack = [];
      
    // Push the current source node
    stack.push(s);
      
    while(stack.length != 0)
    {
         
        // Pop a vertex from stack and print it
        s = stack.pop();
         
        // Stack may contain same vertex twice. So
        // we need to print the popped item only
        // if it is not visited.
        if (visited[s] == false)
        {
            document.write(s + " ");
            visited[s] = true;
        }
          
        // Get all adjacent vertices of the
        // popped vertex s. If a adjacent has 
        // not been visited, then push it
        // to the stack.
        for(let node = 0; 
                node < this.adj[s].length;
                node++)
        {
            if (!visited[this.adj[s][node]])
                stack.push(this.adj[s][node])
        }
    }
}
}
 
// Driver code
 
// Total 5 vertices in graph
let g = new Graph(5);
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(1, 4);
 
document.write("Following is the Depth " + 
               "First Traversal<br>");
g.DFS(0);
 
// This code is contributed by rag2127
 
</script>

Output

Following is Depth First Traversal
0 3 2 1 4

Complexity Analysis:
- Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
- Space Complexity: O(V). Since an extra visited array is needed of size V.

Modification of the above Solution: Note that the above implementation prints only vertices that are reachable from a given vertex. For example, if the edges 0-3 and 0-2 are removed, then the above program would only print 0. To print all vertices of a graph, call DFS for every unvisited vertex.

Implementation:

C++

// An Iterative C++ program to do DFS traversal from
// a given source vertex. DFS(int s) traverses vertices
// reachable from s.
#include<bits/stdc++.h>
using namespace std;
 
// This class represents a directed graph using adjacency
// list representation
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // adjacency lists
public:
    Graph(int V);  // Constructor
    void addEdge(int v, int w); // to add an edge to graph
    void DFS();  // prints all vertices in DFS manner
 
    // prints all not yet visited vertices reachable from s
    void DFSUtil(int s, vector<bool> &visited);
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}
 
// prints all not yet visited vertices reachable from s
void Graph::DFSUtil(int s, vector<bool> &visited)
{
    // Create a stack for DFS
    stack<int> stack;
 
    // Push the current source node.
    stack.push(s);
 
    while (!stack.empty())
    {
        // Pop a vertex from stack and print it
        int s = stack.top();
        stack.pop();
 
        // Stack may contain same vertex twice. So
        // we need to print the popped item only
        // if it is not visited.
        if (!visited[s])
        {
            cout << s << " ";
            visited[s] = true;
        }
 
        // Get all adjacent vertices of the popped vertex s
        // If a adjacent has not been visited, then push it
        // to the stack.
        for (auto i = adj[s].begin(); i != adj[s].end(); ++i)
            if (!visited[*i])
                stack.push(*i);
    }
}
 
// prints all vertices in DFS manner
void Graph::DFS()
{
    // Mark all the vertices as not visited
    vector<bool> visited(V, false);
 
    for (int i = 0; i < V; i++)
        if (!visited[i])
            DFSUtil(i, visited);
}
 
// Driver program to test methods of graph class
int main()
{
    Graph g(5);  // Total 5 vertices in graph
    g.addEdge(1, 0);
    g.addEdge(2, 1);
    g.addEdge(3, 4);
    g.addEdge(4, 0);
 
    cout << "Following is Depth First Traversal\n";
    g.DFS();
 
    return 0;
}

Java

//An Iterative Java program to do DFS traversal from
//a given source vertex. DFS() traverses vertices
//reachable from s.
 
import java.util.*;
 
public class GFG 
{
    // This class represents a directed graph using adjacency
    // list representation
    static class Graph
    {
        int V; //Number of Vertices
         
        LinkedList<Integer>[] adj; // adjacency lists
         
        //Constructor
        Graph(int V)
        {
            this.V = V;
            adj = new LinkedList[V];
             
            for (int i = 0; i < adj.length; i++)
                adj[i] = new LinkedList<Integer>();
             
        }
         
        //To add an edge to graph
        void addEdge(int v, int w)
        {
            adj[v].add(w); // Add w to v’s list.
        }
         
        // prints all not yet visited vertices reachable from s
        void DFSUtil(int s, Vector<Boolean> visited)
        {
            // Create a stack for DFS
            Stack<Integer> stack = new Stack<>();
              
            // Push the current source node
            stack.push(s);
              
            while(stack.empty() == false)
            {
                // Pop a vertex from stack and print it
                s = stack.peek();
                stack.pop();
                  
                // Stack may contain same vertex twice. So
                // we need to print the popped item only
                // if it is not visited.
                if(visited.get(s) == false)
                {
                    System.out.print(s + " ");
                    visited.set(s, true);
                }
                  
                // Get all adjacent vertices of the popped vertex s
                // If a adjacent has not been visited, then push it
                // to the stack.
                Iterator<Integer> itr = adj[s].iterator();
                  
                while (itr.hasNext()) 
                {
                    int v = itr.next();
                    if(!visited.get(v))
                        stack.push(v);
                }
                  
            }
        }
         
        // prints all vertices in DFS manner
        void DFS()
        {
            Vector<Boolean> visited = new Vector<Boolean>(V);
            // Mark all the vertices as not visited
            for (int i = 0; i < V; i++)
                visited.add(false);
     
            for (int i = 0; i < V; i++)
                if (!visited.get(i))
                    DFSUtil(i, visited);
        }    
    }
     
    // Driver program to test methods of graph class
    public static void main(String[] args) 
    {
        Graph g = new Graph(5);
        g.addEdge(1, 0);
        g.addEdge(2, 1);
        g.addEdge(3, 4);
        g.addEdge(4, 0);
          
        System.out.println("Following is Depth First Traversal");
        g.DFS();
    }
}

Python3

# An Iterative Python3 program to do DFS 
# traversal from a given source vertex. 
# DFS(s) traverses vertices reachable from s.
class Graph: 
    def __init__(self, V):
        self.V = V 
        self.adj = [[] for i in range(V)]
     
    def addEdge(self, v, w):
        self.adj[v].append(w) # Add w to v’s list.
     
    # prints all not yet visited vertices 
    # reachable from s 
    def DFSUtil(self, s, visited):
         
        # Create a stack for DFS 
        stack = []
     
        # Push the current source node. 
        stack.append(s) 
     
        while (len(stack) != 0):
             
            # Pop a vertex from stack and print it 
            s = stack.pop()
     
            # Stack may contain same vertex twice. 
            # So we need to print the popped item only 
            # if it is not visited. 
            if (not visited[s]):
                print(s, end = " ") 
                visited[s] = True
     
            # Get all adjacent vertices of the 
            # popped vertex s. If a adjacent has not  
            # been visited, then push it to the stack.
            i = 0
            while i < len(self.adj[s]):
                if (not visited[self.adj[s][i]]): 
                    stack.append(self.adj[s][i])
                i += 1
     
    # prints all vertices in DFS manner 
    def DFS(self):
         
        # Mark all the vertices as not visited 
        visited = [False] * self.V
        for i in range(self.V):
            if (not visited[i]):
                self.DFSUtil(i, visited)
 
# Driver Code
if __name__ == '__main__':
 
    g = Graph(5) # Total 5 vertices in graph 
    g.addEdge(1, 0) 
    g.addEdge(2, 1) 
    g.addEdge(3, 4) 
    g.addEdge(4, 0) 
 
    print("Following is Depth First Traversal") 
    g.DFS()
 
# This code is contributed by PranchalK

C#

// An Iterative C# program to do DFS traversal from
// a given source vertex. DFS() traverses vertices
// reachable from s.
using System;
using System.Collections.Generic;
 
class GFG 
{
    // This class represents a directed graph using adjacency
    // list representation
    class Graph
    {
        public int V; // Number of Vertices
         
        public List<int>[] adj; // adjacency lists
         
        // Constructor
        public Graph(int V)
        {
            this.V = V;
            adj = new List<int>[V];
             
            for (int i = 0; i < adj.Length; i++)
                adj[i] = new List<int>();
             
        }
         
        // To add an edge to graph
        public void addEdge(int v, int w)
        {
            adj[v].Add(w); // Add w to v’s list.
        }
         
        // prints all not yet visited vertices reachable from s
        public void DFSUtil(int s, List<Boolean> visited)
        {
            // Create a stack for DFS
            Stack<int> stack = new Stack<int>();
             
            // Push the current source node
            stack.Push(s);
             
            while(stack.Count != 0)
            {
                // Pop a vertex from stack and print it
                s = stack.Peek();
                stack.Pop();
                 
                // Stack may contain same vertex twice. So
                // we need to print the popped item only
                // if it is not visited.
                if(visited[s] == false)
                {
                    Console.Write(s + " ");
                    visited[s] = true;
                }
                 
                // Get all adjacent vertices of the popped vertex s
                // If a adjacent has not been visited, then push it
                // to the stack.
                foreach(int itr in adj[s]) 
                {
                    int v = itr;
                    if(!visited[v])
                        stack.Push(v);
                }
                 
            }
        }
         
        // prints all vertices in DFS manner
        public void DFS()
        {
            List<Boolean> visited = new List<Boolean>(V);
             
            // Mark all the vertices as not visited
            for (int i = 0; i < V; i++)
                visited.Add(false);
     
            for (int i = 0; i < V; i++)
                if (!visited[i])
                    DFSUtil(i, visited);
        } 
    }
     
    // Driver code
    public static void Main(String[] args) 
    {
        Graph g = new Graph(5);
        g.addEdge(1, 0);
        g.addEdge(2, 1);
        g.addEdge(3, 4);
        g.addEdge(4, 0);
         
        Console.WriteLine("Following is Depth First Traversal");
        g.DFS();
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
//An Iterative Javascript program to do DFS traversal from
//a given source vertex. DFS() traverses vertices
//reachable from s.
 
// This class represents a directed graph using adjacency
    // list representation
class Graph
{
     //Constructor
    constructor(V)
    {
        this.V=V;
        this.adj = new Array(V);
        for (let i = 0; i < this.adj.length; i++)
                this.adj[i] = [];
    }
     
    //To add an edge to graph
    addEdge(v,w)
    {
        this.adj[v].push(w); // Add w to v’s list.
    }
     
     // prints all not yet visited vertices reachable from s
    DFSUtil(s,visited)
    {
        // Create a stack for DFS
            let stack = [];
               
            // Push the current source node
            stack.push(s);
               
            while(stack.length != 0)
            {
                // Pop a vertex from stack and print it
                s = stack.pop();
                 
                   
                // Stack may contain same vertex twice. So
                // we need to print the popped item only
                // if it is not visited.
                if(visited[s] == false)
                {
                    document.write(s + " ");
                    visited[s] = true;
                }
                   
                // Get all adjacent vertices of the popped vertex s
                // If a adjacent has not been visited, then push it
                // to the stack.
                 
                   
                for (let itr=0;itr<this.adj[s].length;itr++)
                {
                    let v = this.adj[s][itr];
                    if(!visited[v])
                        stack.push(v);
                }
                   
            }
    }
     
    // prints all vertices in DFS manner
    DFS()
    {
        let visited = []
            // Mark all the vertices as not visited
            for (let i = 0; i < this.V; i++)
                visited.push(false);
      
            for (let i = 0; i < this.V; i++)
                if (!visited[i])
                    this.DFSUtil(i, visited);
            
    }
     
}
 
// Driver program to test methods of graph class
let g = new Graph(5);
g.addEdge(1, 0);
g.addEdge(2, 1);
g.addEdge(3, 4);
g.addEdge(4, 0);
 
document.write("Following is Depth First Traversal<br>");
g.DFS();
 
 
 
// This code is contributed by avanitrachhadiya2155
</script>

Output

Following is Depth First Traversal
0 1 2 3 4

Time complexity: O(V+E), The time complexity of DFS is O (V+E). Here V is the number of vertices and E is the number of edges.
Auxiliary Space: O(V), The space complexity of DFS is O(V). The space is consumed by the recursion stack and the visited array.

S

Shivam

Improve

Previous Article

Java Program for Depth First Search or DFS for a Graph

Applications, Advantages and Disadvantages of Depth First Search (DFS)

Similar Reads

Iterative Deepening Search(IDS) or Iterative Deepening Depth First Search(IDDFS)

There are two common ways to traverse a graph, BFS and DFS. Considering a Tree (or Graph) of huge height and width, both BFS and DFS are not very efficient due to following reasons. DFS first traverses nodes going through one adjacent of root, then next adjacent. The problem with this approach is, if there is a node close to root, but not in first

Depth First Traversal ( DFS ) on a 2D array

Given a 2D array grid[][] of dimension N * M, the task is to perform the Depth - First Search traversal on the given 2D array. Examples: Input: grid[][] = {{-1, 2, 3}, {0, 9, 8}, {1, 0, 1}}Output: -1 2 3 8 1 0 9 0 1Explanation: The sequence of traversal of matrix elements using DFS is -1, 2, 3, 8, 1, 0, 9, 0, 1. Input: grid[][] = {{1, 2, 3}, {5, 6,

Depth First Search or DFS for disconnected Graph

Given a Disconnected Graph, the task is to implement DFS or Depth First Search Algorithm for this Disconnected Graph. Example: Input: Output: 0 1 2 3 Algorithm for DFS on Disconnected Graph:In the post for Depth First Search for Graph, only the vertices reachable from a given source vertex can be visited. All the vertices may not be reachable from

Depth First Search or DFS for a Graph

Depth First Traversal (or DFS) for a graph is similar to Depth First Traversal of a tree. The only catch here is, that, unlike trees, graphs may contain cycles (a node may be visited twice). To avoid processing a node more than once, use a boolean visited array. A graph can have more than one DFS traversal. Example: Input: n = 4, e = 6 0 -> 1,

Sum of nodes at maximum depth of a Binary Tree | Iterative Approach

Given a root node to a tree, find the sum of all the leaf nodes which are at maximum depth from the root node. Example: 1 / \ 2 3 / \ / \ 4 5 6 7 Input : root(of above tree) Output : 22 Explanation: Nodes at maximum depth are 4, 5, 6, 7. So, the sum of these nodes = 22 Approach: There exists a recursive approach to this problem. This can also be so

Iterative Boundary Traversal of Complete Binary tree

Given a complete binary tree, traverse it such that all the boundary nodes are visited in Anti-Clockwise order starting from the root. Example: Input: 18 / \ 15 30 / \ / \ 40 50 100 20 Output: 18 15 40 50 100 20 30 Approach: Traverse left-most nodes of the tree from top to down. (Left boundary)Traverse bottom-most level of the tree from left to rig

Iterative Postorder traversal | Set 3

We have seen different ways of performing postorder traversal on Binary Trees. Post Order Traversal.Iterative Postorder Traversal using Two Stacks.Iterative Postorder Traversal using One Stack. Here is another way of performing the postorder traversal on a Binary Tree iteratively using a single stack.Consider the Below Terminologies: 0 - Left eleme

Iterative Postorder Traversal of N-ary Tree

Given an N-ary tree, the task is to find the post-order traversal of the given tree iteratively.Examples: Input: 1 / | \ 3 2 4 / \ 5 6 Output: [5, 6, 3, 2, 4, 1] Input: 1 / \ 2 3 Output: [2, 3, 1] Approach:We have already discussed iterative post-order traversal of binary tree using one stack. We will extend that approach for the n-ary tree. The id

Check if a binary tree is subtree of another binary tree using preorder traversal : Iterative

Given two binary trees S and T, the task is the check that if S is a subtree of the Tree T. For Example: Input: Tree T - 1 / \ 2 3 / \ / \ 4 5 6 7 Tree S - 2 / \ 4 5 Output: YES Explanation: The above tree is the subtree of the tree T, Hence the output is YES Approach: The idea is to traverse both the tree in Pre-order Traversal and check for each

Iterative diagonal traversal of binary tree

Consider lines of slope -1 passing between nodes. Given a Binary Tree, print all diagonal elements in a binary tree belonging to the same line. Input : Root of below tree Output : Diagonal Traversal of binary tree : 8 10 14 3 6 7 13 1 4Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. We have discussed the recursiv

Article Tags :

Practice Tags :