hii had this question in my interview:you are given an n-ary tree.you are given its root R and a node N.the problem is to determine if u can lock the node N, given the constraints:1) you cannot lock a node if any of its ancestors is locked.
that is, if you lock a node N, then any node S in the
This can be solved by two DFS traversals.The first from the root to the node N. Here you will get the path from root to N. Just go along the path and see whether there is any locked node. If there is a locked node then you cannot lock node N.
Next you do a complete DFS of the subtree starting
hiya thats what i too thought.but the interviewer insisted that theres a better algohe gave a hint as : keep a count in each node, which specifies the number of locks in the subtree rooted at that node
On 3/24/06, Dhyanesh [EMAIL PROTECTED] wrote:
This can be solved by two DFS traversals.The first
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
Hi all,I think there can be one more solution... where a BFS is folowed by DFS works.Algo 2:IsLockable(Node N){ queue Q; if(root is not locked) Q.insert(root); while(!Q.empty()) {
Node n = Q.removeHead(); if(n == N) return DFS(n); for(each child a of N) If(a is not locked) Q.insert(a); } return
Hi all,The third solution is... (I hope there will not be any fourth ;) )Two BFSs...1. The first BFS will traverse all unlocked nodes (same as solution one)...2. The second BFS will traverse until one locked node is encountered.
Hey, guys... this is boring...It is always possible to convert
