Binary Tree Level-Order Traversal Using Depth First Search (DFS) [Not to USE BFS]

Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level. Breadth First Search (BFS) is not allowed. We have already seen how to do level order traversal here.

Example
So consider the tree:
      1
   /    \
  2      3
 /   \   /    \
4   5  6   7
The BFS or level order traversal here is :
1 2 3 4 5 6 7

Last time we used BFS, but this time it is not allowed.

Hint:
Write a function call printLevel(BinaryTree *p, int level) which will print all nodes of a given level. Assume you know the height of the tree, then you can print the entire tree level by level utilizing printLevel.

Solution:
printLevel function can be solved using DFS. Decrement level by one as you advance to the next level. When level equals 1, you’ve reached the given level. To find the maximum height (or the max depth) of a tree, you can read my post: Maximum Height or Depth of a Binary Tree.

void printLevel(BinaryTree *p, int level) {
  if (!p) return;
  if (level == 1) {
    cout << p->data << " ";
  } else {
    printLevel(p->left, level-1);
    printLevel(p->right, level-1);
  }
}
 
void printLevelOrder(BinaryTree *root) {
  int height = maxHeight(root);
  for (int level = 1; level <= height; level++) {
    printLevel(root, level);
    cout << endl;
  }
}

Further Thoughts:
If you look carefully, you will notice that the DFS solution traverses the same node multiple times. Since BFS traverses each node exactly one time, BFS is much more efficient than DFS.
Could you find the run time complexity for the DFS level-order traversal solution? Try to estimate as best as you can, and then find the correct answer by proving it using Math. Does your estimate fares well with the correct answer? Why?
Answer:
Although the DFS solution traverse the same node multiple times, it is not another order slower than the BFS solution. Here is the proof that the DFS solution above runs in O(N) time, where N is the number of nodes in the binary tree and we assume that the binary tree is balanced.

We first compute the complexity of printLevel for the kth level:

T(k) = 2T(k-1) + c
     = 2k-1 T(1) + c
     = 2k-1 + c

Assuming it’s a balanced binary tree, then it would have a total of lg N levels.
Therefore, the complexity of printing all levels is:

T(1) + T(2) + ... + T(lg N)
= 1 + 2 + 22 + ... + 2lg N-1 + c
= O(N)

Finding the maximum height of the tree also takes O(N) time, therefore the overall complexity is still O(N).

Thanks.

Read More

DFS (Depth first search) for graph

What is dfs?
 This algorithm explores aggressively and backtracks only when necessary. This is similar to how we play a maze game.

To code DFS iteratively, we can mimic BFS , but use a Stack instead of a Queue. Another way to code this would be to do it recursively. DFS is very naturally phased as recursive example. We will see both of implementation later.

 DFS(graph G, vertex s)
     mark s as explored
     for every edge (s, v):
          if v unexplored
               DFS(G, v)

Example : 
Consider the graph:

So, our strategy will be to explore aggressively and only backtrack when necessary.
Example taken from coursera course by Tim Roughgarden in Algorithms: Design and Analysis, Part 1.

Now, we have starting vertex as s.  From s we have to go to some node, lets go to a.

From as we can't go to b, as it is s's immediate neighbor, but we can go to a's immediate neighbor. So we go to c:

From c, we go to e.

From e we can go to d only as it is the only neighbor which is unexplored. So d is 5th node we see.

From d we can either go to c or we can go b. Lets suppose we go to c. But c is already explored at number 3, so we retreat, and we then go to b.

Now at b we go to s, but we have explored that, then we go to a, we have explored. So we have explored all the options from b, so we retreat to d, then we see that at d also we have explored all the options, so we retreat to e, from e to c, from c to a, and then we come to s back. From s we have not went through edge s-b, so we traverse and again retreat as we have already seen b. Now we have covered all the edges.

Basic DFS Properties
At the end of DFS, all vertices that could have been reached will have been reached.
Time complexity - 
Running time for adjacency list- O(|V|+|E|) OR O(n+m) where |V| and |E| is number of vertices and edges for adjacency list representation of graph.
Running time for adjacency matrix - O(|V|²) OR O(n²) as we have to traverse through the whole row until we find an edge.

Application of DFS

1. Topological sorting
2. Finding SCC(strongly connected component)

Read More

Topological Sorting

Definition

Topological sort: an ordering of the vertices in a directed acyclic graph, such that: If there is a path from u to v, then v appears after u in the ordering.

A topological ordering of a directed graph G is a labeling f of G's nodes (1...n) such that:
(1) the f(v)'s are the set {1, 2, ... , n}
(2) if (u, v) in G, then f(u) < f(v) ... the graph should move in forward direction.

Lets understand this with example, consider following graph :

Here we can order s,v,w,t as 1,2,3,4:

OR we can order s,w,v,t as 1,2,3,4 i.e. w coming before v.

So, if we have only 2 topological orders. If we put w before s, we will have to go backwards, and hence this is not topological ordering.

Necessary condition for graph to have topological ordering
So, only restriction on directed graph to have topological ordering is that it shouldn't have cycle.

Consider the graph G with directed cycle, suppose we go forward, and when we pass through cycle, we come back to the same point, hence there is no ordering.

So, if there is no cycle we are guarantee to have topological ordering.

Uniqueness of topological ordering
A topological sort will be unique if and only if there is a directed edge between each pair of consecutive vertices in the topological order (i.e., the digraph has a Hamiltonian path). Source

A Hamiltonian path just means that a path between two vertices will only visit each vertex once, it does not mean though that one vertex must have no incoming edges. You can have a Hamiltonian path that is in fact a cycle. This would still generate a unique topological sort (of course it would be a cycle as well if that is important to you).

Uses of topological sort
Scheduling a sequence of tasks based on their dependency.

Algorithm
Algorithm 1 - Using sink vertex
Before we go to algorithm lets define some terms.

Sink vertex - a vertex that has no outgoing edges.

Note - Every directed acyclic graph (DAG) has a sink vertex.
Proof - Suppose that every vertex has atleast outgoing edge, then we keep following outgoing edge  and as the graph size if finite say n, and because of this we see n+1 vertex, which results in directed cycle, and we have already said that it shouldn't exits. So, the last vertex shouldn't return back, otherwise that will result in cycle.

So if graph has to have a topological order, then its the sink vertex where the order ends.

To compute the topological ordering:

Let v be the sink vertex of Graph G
f(v) = n
recurse on (G-v)

so, lets take the example:
Consider the graph below, where t is the sink vertex(marked with orange circle):

We set, f(t) = 4, and remove it from graph. Now we recurse on G-v :

This time we have 2 sink vertices - w and v. Suppose we set f(w)=3, then we remove it from graph. Then we come to f(v) = 2 and remove it from graph and finally f(s) = 1.

So, we take away the sink vertex again and again, until we have no vertex left. It is pretty fast but lets now see the application of DFS.

Topological ordering algorithm 2 - Using DFS
Here is a slick way to do a topological sorting with DFS:

DFS-Loop doesn't take current vertex and has a global variable current_loop is global variable which is initialized to n, and is reduced by1 each time we finish exploring the new vertex.

DFS-Loop(graph G)

    mark all nodes unexplored

    current_label = n (number of nodes, to keep track of ordering,which we will count down)

    for each v in G
        if v not yet explored
            DFS(G, v)

DFS(graph G, vertex start)
    mark start explored
    for every edge(start, v)
        if v not yet explored
            DFS(G, v)
    set f(start) = current_label
    current_label--

Time Complexity - This algorithm is as fast as DFS, because we have added only 1or 2 steps in it which are very trivial. This will run in linear time because you do a constant amount of time at each node and traverse each edge only once since we keep track of which has or has not been explored. So, we have O(n+m) OR O(|V|+|E|).

Dry running the algorithm:
Consider the following graph :

Lets start dfs at node v, as we can start randomly from any point. If we start from v, only point we can go to is t.

So, we set f(t) = current label, which is currently equal to n, which is number of nodes and it is 4.
Once we are done with t, we backtrack to v, and count down current label by 1, to 3. So, f(v)=3:

Now, we go to s as we have not seen it yet. Now from s, we can go to v or w. But v we have already seen, so we move w, from w to t, but we have been to t. So, we back track to w:

Now from w we backtrack to s:

Correctness
To prove correctness, we need to show that if (u,v) is an edge, then f(u)<f(v)
Case 1 : u visited by DFS before v => recursive call corresponding to v finishes before that of u(since DFS using lifo structure). So, we v will be assigned larger label. Thus f(v) > f(u).

Case 2: If v is visited before u, there is no path (v, u) because otherwise it would be a directed cycle. Then, the recursive call of v gets popped before u even gets put on the stack. Thus f(v) > f(u)

Source

Read More

Graph Search Introduction

Graph search algorithms are important but lets have some motivations.

Motivation behind graph search

Here are few motivations:

1. Minimal Road network - Are there sufficient roads for people to go from one place to another. Imagine, Haridwar is only connected via Delhi and there is a natural calamity, then one way people can reach there for relief etc is via Delhi, resulting in worst disaster management, but suppose it is connected via many places, sending relief will be easier. Similarly we can have mobile network, checking if one place can be called from one place to other.
2. Fun - Another fun part is like movie network, where actors/actress can be nodes and edges can be if co-stars appearing in some movie (Undirected graph)
3. Driving directions - Taking from 1 place to other. 
4. Formulate a plan based on priorities, you can traverse from 1 sub plan to other (Directed graph as order involved). 
5. Solving the sudoku - Solving the sudoku can be though as directed graph pointing to sub-puzzle which is already solved.(Directed graph as order involved) 
6. Compute the pieces or component of the graph - providing us with clustering, structure of the web graph.

Generic Graph Search

Goals:

1. Find everything findable/searchable from a given start vertex. So suppose we are given following graph, then findable vertices from starting vertices s, are t,v,w. Note that x,y,z are not searchable.
   
   
   
   Similarly for directed graph, we will always traverse from s in forward direction. So for graph below, vertex t is not searchable, as we are not going to traverse backward.
   
   
   
   
2. Don't explore anything twice, so goal is to complete it in O(m+n) or O(|V|+|E|)

Note: Connectivity of the graph matters a lot in these algorithms. As, if there is very less connectivity, |E|<<|V| so time complexity is O(|V|)

Generic Algorithm

Input : We are given graph G, with vertex s

It is nice to think that vertices explored as territory conquered, and we have to conquer other territories.

So, we need some boolean to find out whether we conquered that territory or node or not.

To start with, we have conquered start node s.

while (possible)
{
    choose an edge (u,v) with u explored and v unexplored (select any from adjency list)    

    Mark v explored
}

This algorithm works for both directed and un-directed graph.

Proof - There is no such point which is unexplored. 
Will do later.

Implementation of generic algorithms
There are lots implementation of this generic algorithm. What gives rise to multiple algorithms of this general sort is in the ambiguity in choosing the next edge.

• BFS - Breadth First Search
  --Select All the neighbours of node s the starting node, then we go to neighbours of this new layer we just added.
  --It can help use compute shortest paths
  -- Compute connected components of undirected graph
  -- Queue is used, because we have to use fifo(first in first out) data-structure
  More details - here.
• DFS - Depth First Search
  -- Aggressively like a mate, backtrack only when necessary
  -- Compute topological ordering of directed acyclic graph
  --Compute connected components in directed graph and undirected graph
  -- Uses stack as it uses recursion
  More Details - here.

Time-wise both are very good strategy. 

Read More

Graph Traversal Methods

There are two possible traversal methods for a graph:
i. Breadth-First Traversal
ii. Depth-First Traversal

i. Breadth-First Traversal: Traverse all the vertices starting from a given 'start vertex'. Hence, such a traversal follows the 'neighbour-first' principle by considering the following:
- No vertex is visited more than once
- Only those vertices that can be reached are visited

Importantly here, we make use of the Queue data structure. In effect, we house the vertices in the queue that are to be visited soon in the order which they are added to this queue i.e. first-in first-out.

Visiting a vertex involves returning the data item in the vertex and adding its neighbour vertices to the queue. However, we don't carryout any action under following conditions:
- if the neighbour is already present in the queue or if the neighbour has been already visited


ii. Depth-First Traversal: Traverse all the vertices starting from a given 'start vertex'. Hence, such a traversal follows the 'neighbour-first' principle by considering the following:
- No vertex is visited more than once
- Only those vertices that can be reached are visited

Importantly here, we make use of the Stack data structure. In effect, we stack the vertices so that vertices to be visited soon are in order in which they are popped from the stack i.e. last-in, first-out.

Visiting a vertex involves returning the data item in the vertex and adding its neighbour vertices to the stack. However, we don't carryout any action if the following occurs:
- neighbour is already present in the stack or if the neighbour has already been visited


 

Read More

DFS (Depth First Search) on tree or graph

Consider this tree  (which is a graph without a cycle) :

Now DFS means traversing to the depth...and then going up, so here DFS traversal will result in 5 2 -4 3 21 19 25. We can use non recursive as well recursive approach to solve this problem.

A depth first search (DFS) through a tree starts at the root and goes straight down a single branch until a leaf is reached. Then, it continues at the nearest ancestor that hasn't been searched through yet. DFS uses much less memory than BFS since there is no need to store all the nodes on one level. DFS also does not search the lowest level last, so if your target is likely a leaf near the bottom of the tree, DFS will typically run faster than BFS.

Recursive Solution
Depth First Search (DFS) is a generalization of the preorder traversal. Starting at some arbitrarily chosen vertex v, we mark v so that we know we've visited it, process v, and then recursively traverse all unmarked vertices adjacent to v (v will be a different vertex with every new method call). When we visit a vertex in which all of its neighbors have been visited, we return to its calling vertex, and visit one of its unvisited neighbors, repeating the recursion in the same manner. We continue until we have visited all of the starting vertex's neighbors, which means that we're done. The recursion (stack) guides us through the graph.

public void depthFirstSearch(Vertex v)
{
        v.visited = true;

        // print the node

        for(each vertex w adjacent to v)
        {
           if(!w.visited)
           {
              depthFirstSearch(w);
           }
        }
}

DFS on tree:

void treeDFS(node *root)
{
    printf("[%d] ", root->value);
    root->visited = 1;

    if (root->left)
    {
      if(root->left->visited==0)
      {
        treeDFS(root->left);
      }
    }

    if (root->right)
    {
      if(root->right->visited==0)
      {
        treeDFS(root->right);
      }
    }
}

Non Recursive solution
DFS is a first in last out search. It is a recursive process. Recursion uses a stack implicitly. So, a non-recursive version of DFS can be done using a stack. Since we want to hold off visiting a particular node until all of its children are visited, we have to push the node again on the stack. We need to differentiate when we revisit the node ("back-tracking" in recursion) so that we do not push its children again on the stack. For that we use a Hashmap data structure which serves as a flag to denote if a node is already visited and its children are added to the stack.

void dfs_nonrecursive(Node root) : 

    Stack stack = new Stack()
    stack.push(root)
   
    Hashmap visited = new Hashmap()
    while true :
        curr = stack.pop()
        if curr == null:
            break
       
        //if curr has children and curr not in visited
        if (curr.left != null || curr.right != null) && visited.get(curr) == null :
            stack.push(curr)
            stack.push(right)
            stack.push(left)
           
            visited.put(curr)
            continue
       
        curr.printValue()

Time: We visit the non-leaf nodes (n/2) twice and the leaf nodes (n/2) once. So, 2*(n/2) + n/2 = O(3n/2) i.e. still O(n) time.

Space: Hashmap visited saves references to the non-leaf nodes only. For tree of n nodes, visited would saves 2^logn-1 = n/2 still O(n) space. The stack would save only O(logn) nodes.

Read More