CODEWITHSUNDEEP
algorithmgraphtreedepth-first-search
MrYo
MrYo

Reputation: 1817

Detect given graph is Tree or not in LogSpace

This is my code to check if given graph is a tree (BFS). The problem is that when I use stack S, it would not be in logSpace. While going through some references, I think I have to replace stack S by some counters but how?Is there any way to modify this algorithm to run in LogSpace? 

 boolean isTree(G){
            Given: G=(V,E)
            pick first node s
            mark s as visited
            S is empty stack << (Problem-I)
            S.push(v)
            while( S is not empty)
                v = S.pop()
                for all neighbors W of v in G
                    //check if marked as already visited
                    if(W is not parent of v && W is visited)
                        return 0
                    else 
                        mark W as a visited
                        S.push(W)
                end for
            end while
        return true
        }

Upvotes: 0

Views: 328

Answers (1)

Kaidul
Kaidul

Reputation: 15875

You didn't consider the space of visited flag, so I am assuming you're using some data-structure with bit masking property like BitSet for visited.

The stack will take O(logn) space at any time where n is the total number of nodes only if the tree is balanced (the maximum height of the tree won't exceed logn nodes). And in worst case, when the tree is flat (growing only in left or only in right), the space complexity will be O(n). So, there is no guarantee of logarithmic space unless the tree is sure to be a balanced tree.

Moreover, you're assuming the given graph is connected. But if the given graph graph is not connected, this can turn into forest (many trees). So you need to check with every nodes instead of pick first node s and if any node is found un-visited after first round, this is not a tree, its a forest/non-tree graph.

Hope it helps!

Edit

Is there any way to keep track of nodes without using stack?

Without stack, either you need to do recursion/DFS which will take O(n) space in worst case in function stack or you can use Queue/BFS which again will take O(n) space. So No, you need at-least O(n) space when the tree is arbitrary(not guaranteed to be balanced).

You can check the implementation in Java and/or C++ here.

Upvotes: 1

Related Questions