Microsoft Interview Question
SDE1sCountry: United States
Interview Type: In-Person
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 ?
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
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)
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).
@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.
What if input node is "root" of a tree, wont you return "null" as you wont even traverse tree
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) {
if (target == head)
return NULL;
if (target->right != NULL)
return target->right;
else if (target->left != NULL)
return target->left;
else
return find_pred_recurse(head,NULL,target);
}
(struct tree*) find_pred_recurse(struct tree *head, struct tree *current, struct tree*target) {
if ( head != NULL) {
if (head->right == target)
return head->left;
find_pred_recurse(head->left,current,target);
find_pred_recurse(head->right,head->left,target);
if (root->left == target)
return current;
}
}
I liked your approach. but the code don't work for 2 reasons.
1. if (head->right == target)
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.
* Your function signature ???
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;
}
}
}
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.
}
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.
}
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.
}
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.
}
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);
}
}
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;
}
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;
}
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;
}
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
}
To find the postorder predecessor of node u:
- Prasanna May 04, 2013If 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 undefined.