Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
That won't work. The answer is
* Find the node using DFS. This is to get the path to the node from root.
* Reverse all the links from the node to the root. like make the parent node as the child node.
That's all. Very simple.
Why do u need DFS here? Ur right hand is already on target node i.e. You have pointer to that node as an input. Now,
Node* node_to_root(Node* root, Node* new_root)
{
- Remove the link to new_root from the list of children of root.
- Insert root into the list of children of new_root. If new_root already has some children they still continue to be children
}
Well, I don't think the problem is that simple. An N-ary tree means any node of the tree will have at max N children. Suppose the intermediate node which we are making the new root already has N children. Then if we make its earlier parent also its children, then the new root will have N+1 children, which violates the N-ary tree property.
Besides to reverse the pointers we need to have parent pointers, which means we have to change tree structure as well.
Reposting the above comment:
Well, I don't think the problem is that simple. An N-ary tree means any node of the tree will have at max N children. Suppose the intermediate node which we are making the new root already has N children. Then if we make its earlier parent also its children, then the new root will have N+1 children, which violates the N-ary tree property.
Besides to reverse the pointers we need to have parent pointers, which means we have to change tree structure as well.
I guess it is that simple only, i.e. all that is needed to be done is to reverse the pointers of the node from root to the node that is being held in the right hand, that's all. And important thing is that the condn of n-ary tree will not break because for each node whose pointer is being reversed is actually loosing one child is also gaining one child as well. But yes for that one particular node i.e. the one being held in right hand, it could be an issue is if it is already having n children.
two steps
- Anonymous October 21, 2011firstly, find right node's parent
secondly, change parent to the right node's child