[algogeeks] Re: tree lock problem

[Prunthaban Kanthakumar]

Hi All,
If I have understood the question correctly, then this will work!

  DFS is recursive. So even though our tree has no parent pointers, we will get such a 'pointer for free' , due to recursion. (Remember recursion allows you to pass information from child to parent)

So a single highly pruned DFS is suffice.

Algo:boolean DFS(node)
(Let X be a global boolean which says whether N is in that subtree or not. Initially X is false)

1. If (node is locked)
       return true;
2. flag = false;
1. for each a in child
    b = DFS(a)
    If (X == true)
        return b;
    flag = flag OR b
2. If (a == N)
       X = true;
3. return flag

If DFS(root) returns false, you can lock N

(My algo will terminate if the root is locked. But.. considering the interviewer's hint... to count the no. of locks, we cannot stop at the root)

We need to prove two facts to establish the correctness of my algorithm.

FACT 1: DFS(root) will not return false if the DFS returns without reaching N.

Proof: DFS(root) will return without reaching N only if it encounters a locked node which is an ancestor of N. In this case the returned value is 'true'. Also we use
flag = flag OR b
So only one 'true' is enough to make the return value true.
When N is not countered at all, the return value will be that of flag. So the return value is always true if N is not encountered in the DFS.

FACT 2: DFS(root) will return false, if all descendents and ancestors of N are not locked.

Proof: When we explore the subtree rooted at N, the value of X will be false (note: X is set to True only after N's descendent's are visited). So, the return value from N will be false only if all descendents are not locked.
Once X is set to true... (as long as the ancestor is not locked) the return value will be the return value from N.

Regards,
Prunthaban
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---