## Microsoft Interview Question for SDE1s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

To fi nd the postorder predecessor of node u:
If u has a right child, r, then pred(u) is r.
Otherwise If u has a left child, l, then pred(u) is l.
Otherwise if u has a left sibling, ls, then pred(u) is ls
Otherwise if u has an ancestor, v, which is a right child and has a left sibling,
vls, then pred(u) is vls
Otherwise, pred(u) is unde fined.

Comment hidden because of low score. Click to expand.
0

Good solution --
two points
a) "Otherwise if u has a left sibling, ls, then pred(u) is ls" : -- In typical scenario, a Binary Tree doesn't keep information about their sibling, so this is an extra information the BTree nodes has to keep.
b) "Otherwise if u has an ancestor, v, which is a right child and has a left sibling, vls, then pred(u) is vls " -- this needs a O(N) processing time.

However, your first 2 points actually cover all the nodes except the leaf nodes. So, perhaps we should first do the first 2 check and if we found that the node is a Leaf node we will do a O(N) post order tree traversal.
what do you think ?

Comment hidden because of low score. Click to expand.
0

Last two points are not correct. If by sibling you mean the node that is in same level and comes before this node in level order traversal consider this tree

``````12
/     \
10     11
/      \
6         9
/     \           \
2      5            8
/      /  \              \
1     3    4             7``````

Here sibling of node 3 is 1. But pred is 2. I think for any target node, if v is a ancestor which has a left child, lc, then lc will be the pred

Comment hidden because of low score. Click to expand.
2
of 2 vote

The simplest way is to save the predecessor in a variable, and then update it while traversing the BT with post-order.
1) set predecessor = null
2) traverse BT with post-order
3) if current_node == input_node {
return predecessor;
} else {
predecessor = current_node
}
4) goto step 3)

Comment hidden because of low score. Click to expand.
1
of 1 vote

This solution works for the given problem, but if I say the given tree is balanced, your algorithm will run in O(n) time while Prasanna's algorithm will run in O(logn).

Comment hidden because of low score. Click to expand.
1
of 1 vote

@Epic_coder, I think you should say binary search tree :)

Comment hidden because of low score. Click to expand.
0

@Epic_coder i think there will be a logn extra space required for storing the pointers to parents of each node in Prasanna's algo.

Comment hidden because of low score. Click to expand.
0

Awesome simple logic dude :)

Comment hidden because of low score. Click to expand.
0

What if input node is "root" of a tree, wont you return "null" as you wont even traverse tree

Comment hidden because of low score. Click to expand.
0

@epic_coder instead of storing pointers to parent v can use a recursive soln which 'll be storing pointers in in-built stack . but again it requires o(log n) space for recursion but code will look simple with recursion.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Logic
1. if non leaf node and it has a right child return right child as pred
2. if non leaf node and it has a left child but no right child return left child as pred
3. if leaf node, iterate from root and track current pred at that instance
3.1 if in a root and target is the right child then a left child is the pred for the right child.
3.2 go to left sub-tree, current is still the current pred
3.3 go to right sub-tree, root-left is the current current pred for the right sub-tree
3.4 if the target is root-left, return current
(Note : 3.4 can be between 3.1 and 3.2. I have put it at the last to have a better understanding and because of which you might go few extra iterations :) )

``````(struct tree *) pred(struct tree *head, struct tree *target) {
return NULL;
if (target->right != NULL)
return target->right;
else if (target->left != NULL)
return target->left;
else
}

(struct tree*) find_pred_recurse(struct tree *head, struct tree *current, struct tree*target) {
if ( head != NULL) {
if (root->left == target)
return current;
}
}``````

Comment hidden because of low score. Click to expand.
0

I liked your approach. but the code don't work for 2 reasons.
return head->left; // head left is the right value to return but due to recursion when it pops the oldest stat from stack, you will lose the value and end up returning wrong answer (ancestor node). check my code below for this fix.

2. construct this tree and check it. tree input(7,4,10,5,3,8,14,9,13,16) where its post-order traversal out put is (3,5,4,9,8,13,16,14,10,7). try to get the predecessor of 9. your approach will fail. so does mine.

``````void pred(node *root, node * &pre, node *nd){
if (root == NULL)
return;
if (nd->right != NULL){
pre = nd->right;
return;
}
if (nd->left != NULL){
pre = nd->left;
return;
}
getPostorder(root, NULL, nd, pre);
}
void find_pred_recurse(node *root, node *parent, node *nd, node *&pre){
if (root != NULL){
if (root->right == nd){
pre = root->left;
return;
}
find_pred_recurse(root->left, NULL, nd, pre);
find_pred_recurse(root->right, root->left, nd, pre);
if (root->left == nd){
pre = parent
return;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

do Preorder traversal.
if found key{
if node have right child, right child is Post Pred, if only left child, postPrd = left child.
if node is leaf node, just return PostPred variable is holding the right Postpredcessor from the second recursion call which below
}
if(value < root->data)
recursively call the left sub tree
else if (value > root->data){
check if root have left child, if so set postorderPred to root->left.
}

Comment hidden because of low score. Click to expand.
0

do Preorder traversal.
if found key{
if node have right child, right child is Post Pred, if only left child, postPrd = left child.
if node is leaf node, just return PostPred variable is holding the right Postpredcessor from the second recursion call which below
}
if(value < root->data)
recursively call the left sub tree
else if (value > root->data){
check if root have left child, if so set postorderPred to root->left.
}

Comment hidden because of low score. Click to expand.
0

do Preorder traversal.
if found key{
if node have right child, right child is Post Pred, if only left child, postPrd = left child.
if node is leaf node, just return PostPred variable is holding the right Postpredcessor from the second recursion call which below
}
if(value < root->data)
recursively call the left sub tree
else if (value > root->data){
check if root have left child, if so set postorderPred to root->left.
}

Comment hidden because of low score. Click to expand.
0

do Preorder traversal.
if found key{
if node have right child, right child is Post Pred, if only left child, postPrd = left child.
if node is leaf node, just return PostPred variable is holding the right Postpredcessor from the second recursion call which below
}
if(value < root->data)
recursively call the left sub tree
else if (value > root->data){
check if root have left child, if so set postorderPred to root->left.
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Prasanna: Nice solution..Can you also provide code with this?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the code for Prasanna's algorithm

``````Node* par_array[100];/*array stores the parents of the node in the call stack which takes up log N space complexity, for simplicity here I am not using dynamic array*/
Node* pred(Node* curr, int item, int level=0){

if(curr==NULL) return NULL;

else{
if(curr->data == item){
if(curr->right!=NULL)		return curr->right;

else if(curr->left!=NULL)	return curr->left;

else if(!par_array.isEmpty()){
Node* par;
while(level>=0){
par = par_array[level-1];
if(par->left!=NULL) return par->left;
}
if(level < 0) return NULL;
}

else 	return NULL;
}

return pred(curr->left, item, level+1);
return pred(curr->right, item, level+1);
}
}``````

Comment hidden because of low score. Click to expand.
0

Ashish and others, please provide code for getting the parents of the item node stored in an array, par_array. Thanks.

Comment hidden because of low score. Click to expand.
0
of 0 vote

node* postOrderPred(node* root,int val,int *found){
if(!root) return NULL;
if(val<root->data)
return postOrderPred(root->left,val,found);
if(val>root->data){
node* t;
if(t=postOrderPred(root->right,val,found))
return t;
if(*found && root->left)
return root->left;
}
else{
*found=1;
if(root->right)
return root->right;
if(root->left)
return root->left;
}
return NULL;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple straightforward code using recursion. However, it could be become tricky if interviewer only wants iterative code

``````void postorder(TreeNode* root, TreeNode* key, TreeNode* ans, TreeNode* prev)
{
if (root != NULL)
{
postorder(root->left, key, prev, ans);
postorder(root->right, key, prev, ans);
if (root == key) { ans = prev; return ; }
else { prev = root ; }
}
}
TreeNode* precessor(TreeNode* node, TreeNode* key)
{
TreeNode* ans(NULL), prev(NULL);
predecessor(node, key, ans, prev);
return ans;
}``````

Comment hidden because of low score. Click to expand.
0

signature for postorder is wrong

``void postorder(TreeNode* root, TreeNode* key, TreeNode*& ans, TreeNode*& prev) ;``

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````PBTree GetPostOrderPredecessor(PBTree pRoot, PBTree pNode)
{
PBTree pPred = NULL;
PBTree pRightSubtree = NULL;
CStack<PBTree> stack;
bool fFound = false;

if (pRoot && pNode)
{
if (pNode->Right)
{
pPred = pNode->Right;
}
else
{
if (pNode->Left)
{
pPred = pNode->Left;
}
else
{
// complex case for leaf
stack.Push(pRoot);

while (!stack.IsEmpty())
{
while (pRoot->Left)
{
stack.Push(pRoot->Left);
pRoot = pRoot->Left;
}

while (!stack.IsEmpty())
{
pRoot = stack.Pop();

if (pRoot->Right != NULL && pRoot->Right != pRightSubtree)
{
stack.Push(pRoot);
stack.Push(pRoot->Right);
pRoot = pRoot->Right;
}
else
{
if (pRoot != pNode)
{
pPred = pRoot;
}
else
{
fFound = true;
break;
}
pRightSubtree = pRoot;
}
}

if (fFound)
{
break;
}
}
}
}
}

return pPred;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

void pred (node*node)
{
if (node==NULL)
return ;

int old=node->data;
pred(node->left);
pred(node->right);
if(node->data==inputdata)
cout<<old;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Post-order predecessor is nothing but its left child. (last post order visited element in left sub tree)

struct BinaryTree *PostorderPredecessor(struct BinaryTree *node) {
return node->left
}

Comment hidden because of low score. Click to expand.
0

No. right children of the given node - if right sub tree exist. otherwise left node is the answer.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.