Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Rockstar - nice! Swathi, the code is correct and purposely from right to left.
Here is a solution without a static variable:
Node * InOrderModify(Node * pNode, Node * pPrev)
{
if (pNode == NULL)
return pPrev;
pPrev = InOrderModify(pNode->pLeft, pPrev);
if (pPrev != NULL)
pPrev->pSucc = pNode;
return InOrderModify(pNode->pRight, pNode);
}
@czpete425: Thanks a lot to you too! Your solution without static variable is just awesome! You should have entered that as an answer so I could upvote it!
@czpete425.. thnx buddy,its a vry gud approach.. gud going..
@mag thanku dear friend....
@swathi.. swathi,work it out on a tree.. u will get d difference,nd yar as i said inorder is been modified
@czpete425 I have a question
pPrev = InOrderModify(pNode->pLeft, pPrev)
pPrev is Null till you reach a node with no left child...
should it not be
pPrev = InOrderModify(pNode->pLeft, pNode)
@czpete425 can you please explain how do you set syccessor in followng case
4
1 6
we call ur fnct with InOrderModify(4,NULL)
it again calls InOrderModify(1,NULL)
then InOrderModify(NULL NULL) and return NULL)
prev=NULL
then InOrderModify(6,4) again return 4
4->setSucc(6) which is again wrong
Please check my suggestion..and point out mistakes(I am sure there are, I am beginner)
Node * InOrderModify(Node * pNode, Node * pPrev)
{
if (pNode == NULL)
return pPrev;
pPrev = InOrderModify(pNode->pLeft, pNode);
if (pPrev != NULL)
pPrev->pSucc = pNode;
return InOrderModify(pPrev->pRight, pNode);//prb here
}
@Anonymous: pPrev is the in-order predecessor not the parent. And you are absolutely correct - if you start at the root and keep going to left childrent only, the current node is the smallest thing you have seen so far, hence no in-order predecessor. Once you backtrack or go to right child, you're no longer the smallest, hence pPrev is not NULL.
@shallysahi: Try stepping through the code one line at a time and write down all the variables. At the same time remember where you are for each recursion. Something like this:
InOrderModify(4, NULL) // Initial call
// pNode = 4, pPrev = NULL
InOrderModify(1, NULL) // From line 5
// pNode = 1, pPrev = NULL
InOrderModify(NULL, NULL) // From line 5
// pNode = NULL, pPrev = NULL
return NULL
InOrderModify(NULL, 1) // From line 8
// pNode = NULL, pPrev = 1
return 1
return 1
// pNode = 4, pPrev = 1
set Succ(1) = 4 // Line 7
InOrderModify(6, 4) // Line 8
// pNode = 6, pPrev = 4
InOrderModify(NULL, 4) // Line 5
return 4
// Still pNode = 6, pPrev = 4
Succ(4) = 6 // Line 7
InOrderModify(NULL, 6)
// pNode = NULL, pPrev = 6
return 6
return 6;
return 6;
Hopefully this will make things more clear ... Also, you can try running the code in a debugger ...
@czpete425 I have one question where pPrev pointer is modified. If i call it InOrderModify(root,NULL);
@MI: InOrderModify(pRoot, NULL) is exactly how you should call this function. If you do, and assuming that pRoot != NULL, you keep calling
pPrev = InOrderModify(pNode->pLeft, pPrev);
recursively until you find a node with no left child. Then pPrev becomes that node because you call
pPrev = InOrderModify(pNode->pLeft, pNode);
Void InorderSuccessor(node* root, node* pre)
{
if(!root)
return;
InorderSuccessor(root->left,pre)
if(pre)
pre->succ = root;
pre = root;
InorderSuccessor(root->right,pre);
}
I had a hard time parsing the algorithm presented at the top of the page, that uses no temp variable. Eventually, I went back to the basics of recursion and figured out how the algorithm works. Thought I'll present my analysis here in case it can be of use.
Let us assume we are at a Node n. There are two parts to this solution: 1) make n as the successor of a node in the left child tree 2) make a node in the right child tree a successor of n.
Lets write the algorithm for the 1st case. Assume a recursive call into the left child tree returns a node whose successor is n. We then set n as the successor of this node, then we make a recursive call into the right child tree. The node that is returned from this call, we pass up to the level above. For the base case, when we reach the leaf node, we simply return this node. Lets write code for this:
public Node inOrderSuccessor(Node n) {
if (n.left == null && n.right == null) {
return n;
}
Node prev = inOrderSuccessor(n.left);
prev.successor = n;
return inOrderSuccessor(n.right);
}
Now, on to the 2nd case. The successor of Node n is the first node in the right child tree with no left child. We must pass n into the recursive call and set its successor when the above condition is reached.
public Node isOrderSuccessor(Node n, Node firstAncestorWithRightChild) {
if (n.left == null) [
firstAncestorWithRightChild.successor = n;
}
if (n.left == null && n.right == null) {
return n;
}
Node prev = inOrderSuccessor(n.left, firstAncestorWithRightChild);
prev.successor = n;
return inOrderSuccessor(n.right, n);
}
Hope this is useful.
we just need to modify the inorder traversal.. thats it
- rockstar November 09, 2012call this function from main with calling as inordermodify(root);
void inordermodify(struct node *head)
{
static node *temp= NULL;
if(head != NULL)
{
inordermodify(head->right);
head->inordersucc = temp;
temp = head;
inordermodify(head->left);
}
}