dfs, bfs without recursion

BFS (Breath First Search) without recursion:

BFS is a first in first out search. So, a non-recursive version of BFS can be done using a queue.

bfs_nonrecursive(root) : 
    q = new
    q.enqueue(root)
    while (!q.isempty()): 
        n = q.dequeue()
        process(n)
        if n.left != null:
            q.enqueue(n.left)
        if n.right != null:
            q.enqueue(n.right)

Time: Since each node is visited once, O(n) time is required.

Space: We save the nodes at each level. We have to save a maximum of n/2 nodes for the last level. i.e. O(n) space is needed.


DFS (Depth First Search) without recursion:

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 ("backtracking" in recursion) so that we do not push its children again on the stack. For that we use statuses.

both -> right -> none
|                 ^
------------------|

dfs_nonrecursive(root):
    stack s = new 
    s.push({root, "both"})
    while !s.isempty():
        n, process = s.pop()
        // left
        if process == "left" || "both":
            if n.left != null:
                s.push({n, "right"})
                s.push({n.left, "both"})
                continue
        // n
        if process != "none":
            process(n)
        // right
        if process == "right" || "both":
            if n.right != null:
                s.push({n, "none"})
                s.push({n.right, "both"})
                continue

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: The stack would save only logn nodes, O(logn) space.