Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
void BST::replaceRootWithLastLeafUsingBFS()
{
if ( ! root_ || isLeaf(root_) )
return;
queue<Node*> Q;
Q.push(root_);
Node *last_parent = NULL, *last_child = NULL;
while(!Q.empty())
{
Node* node = Q.front();
Q.pop();
if(isLeaf(node))
last_child = node;
else
last_parent = node;
if ( node->left_ )
Q.push(node->left_);
if( node->right_ )
Q.push(node->right_);
}
/* swap last_child with root*/
if ( last_parent->left_ == last_child )
last_parent->left_ = root_;
else
last_parent->right_ = root_;
last_child->left_ = root_->left_;
last_child->right_ = root_->right_;
root_->left_ = NULL;
root_->right_ = NULL;
root_ = last_child;
}
well its something like this
A
B C
D E
so here A is root which has two child as B & C. And B has two child D & E. There are no child of C. So the output should be
F
B C
D A
Anybody going to try posting an algo?
The tricky part of this is finding the parent of the rightmost node. This is easy in a heap structure. For any given element, its parent is going to be index / 2. So create a list<T> of Nodes. The root node is added twice (to make the root node index 1 and not zero to preserve the heap parent / child calculation). Set an enumerator to the List's 1st position. "Pop" the first position by Pushing each child node of the current node onto the list, then advance the enumerator one position. Continue doing so until all nodes are on the list. The last node will be at List.Count -1; Its parent node will be (List.Count - 1) / 2; Examine that parent node to find out if it has a right node. If not, the root node is added to the parent's left side. If it does have a right node, the root node is added to the parent's right side. The last node's left and right pointer are set to the root's left and right. The new rightmost node's left and right pointer are set to null.
won't using a function like this work to swap last node in the queue and root node(that is already stored as head)
function call: last_node=replace(head,last_node);
.
and function definition goes like this:
node * replace(node *head, node *curr_node)
{
node *root=head;
head=curr_node;
return head;
}
public void exchangeLastwithFirst(TreeNode node)
{
if(node == null)
return;
if(node.getLeft()!=null)
queue.insert(node.getLeft());
if(node.getRight()!=null)
queue.insert(node.getRight());
if(queue.getSize()!=1)
exchangeLastwithFirst(queue.remove());
else
{
Char temp = queue.peek().getData();
queue.remove().setData(this.root.getData());
this.root.setData(temp);
}
}
- anonymous June 28, 2012