Microsoft Interview Question
Software Engineer / DevelopersYes, typical binary tree - each node has a left and right node pointer, as well as a pointer to it's parent.
Anonymous - you cannot take as a parameter the root.
My solution (after being told that I cannot store each parent in a hash table was to raise the lower of the 2 nodes to the level of the other node, and traverse up the tree until r->parent == l->parent)
another one:-
Node * LCA(Node *t , Node *n1,Node * n2)
{
if (!t) return NULL ;
if ((n1->val < t->val)) && (n2->val < t->val))
return LCA(t->left,n1,n2);
if ((n1->val > t->val)) && (n2->val > t->val))
return LCA(t->right,n1,n2);
if ( (n1->val <= t->val)) && (n2->val >= t->val))
return t;
}
is this right ? i am not sure .. since it seems its doing compares, it seems the question clearly states that its not a BST and its a normal binary tree.
is this right ? i am not sure .. since it seems its doing compares, it seems the question clearly states that its not a BST and its a normal binary tree.
I hate this captcha, they are keeping the images so complex that it takes 5-6 tires to get it right .. please remove this .. its more of a pain than useful.
node* LCA(node* nd1, node* nd2){
node* cur1 = nd1;
node* cur2 = nd2;
// calculate nd1 height
int nd1_height = 0;
while(cur1->parent!=NULL){
nd1_height++;
cur1 = cur1->parent;
}
// calculate nd2 height
int nd2_height = 0;
while(cur2->parent!=NULL){
nd2_height++;
cur2 = cur2->parent;
}
int diff = nd1_height - nd2_height;
cur1 = nd1;
cur2 = nd2;
if(diff>0){
while(diff--){
cur1 = cur1->parent;
}
} else{
diff = -diff;
while(diff--){
cur2 = cur2->parent;
}
}
while(1){
if(cur1==NULL || cur2==NULL) break;
if(cur1 == cur2)
return cur1;
cur1 = cur1->parent;
cur2 = cur2->parent;
}
return NULL;
}
This is a very good algorithm - to figure out the depths and then 2 pointers. Runtime is O(h) - h is the tree height
while calculating the height of node1 and node2...we can check if the other node comes on the way to the root...if yes then return that immediatley...
also i see another solution that talks about parent pointer. Does a normal binary tree have parent pointer ? no is the clear answer.
So the solution should be for a Binary Tree (not BST) , (of course that can be unbalanced, and incomplete)), which means there is only a left and right pointer. No parent or up, no rule that left should be less than parent and right greater than parent. - so a simple binary tree.
Somehow people have byhearted solutions and they dump that in interviews and they get selected.
toobad,
let us consider the worst case of the nodes not having the pointers to its parents, the tree is unbalanced and incomplete . And, ofcourse, it is not a BST..do you have any solution my your mind..this would definitely increase the complexity of the problem...I am working on it...If I get a solution, I would definitely post it here.
toobad,
let us consider the worst case of the nodes not having the pointers to its parents, the tree is unbalanced and incomplete . And, ofcourse, it is not a BST..do you have any solution in your mind..this would definitely increase the complexity of the problem...I am working on it...If I get a solution, I would definitely post it here.
(a typo in my previous comment)
what anonymous said is true,but I was not able to come up with a solution for a binary tree. So the following program is assuming a BST and the program is to find the common nodes of the two nodes given.
/*Given 2 nodes in a binary tree (not a binary search tree), find the first common parent node.
You are not allowed to store any nodes in a data structure.*/
#include <stdio.h>
#include <stdlib.h>
struct NODE{
int data;
struct NODE* left;
struct NODE* right;
};
typedef struct NODE* node;
node constructBST(node root,int data){
node cur,mytemp;
if(!root){
node temp;
temp=(node)malloc(sizeof(struct NODE));
temp->data=data;
temp->left=NULL;
temp->right=NULL;
root=temp;
return root;
}
cur=root;
while(cur->data>data){
if(cur->left)
cur=cur->left;
else
break;
}
while(cur->data<=data){
if(cur->right)
cur=cur->right;
else
break;
}
if(data<cur->data){
mytemp=(node)malloc(
sizeof(struct NODE));
mytemp->data=data;
mytemp->left=NULL;
mytemp->right=NULL;
cur->left=mytemp;
}
if(data>cur->data){
mytemp=(node)malloc(
sizeof(struct NODE));
mytemp->data=data;
mytemp->left=NULL;
mytemp->right=NULL;
cur->right=mytemp;
}
return root;
}
int deapth(node root, node node1){
node cur;
int len=0;
if(!root){
printf("\nEmpty list");
return(0);
}
cur=root;
while(node1->data<=cur->data){
if(cur->left){
cur=cur->left;
len++;
}
else
break;
}
while(node1->data>cur->data){
if(cur->right){
cur=cur->right;
len++;
}
else break;
}
return len;
}
node findCommonParent(node root,node node1,node node2){
int data1,data2;
node larger,smaller;
node cur;
cur=root;
if(!cur){
printf("\nEmpty List");
return NULL;
}
data1=node1->data;
data2=node2->data;
if(data1>data2){
larger=node1;
smaller=node2;
}
else{
larger=node2;
smaller=node1;
}
while(cur->data > larger->data){
if(cur->left)
cur=cur->left;
else
break;
}
while(cur->data <= smaller->data){
if(cur->right)
cur=cur->right;
else
break;
}
//printf("\n The common parent is %d ",cur->data);
return cur;
}
int main()
{
int i=0;
node root,commonParent,node1,node2;
commonParent=NULL;
root=NULL;
node1=(node)malloc(sizeof(struct NODE));
node2=(node)malloc(sizeof(struct NODE));
node1->data=1;
node2->data=3;
i=5;
root=constructBST(root,i);
i=2;
root=constructBST(root,i);
i=3;
root=constructBST(root,i);
i=1;
root=constructBST(root,i);
i=9;
root=constructBST(root,i);
i=7;
root=constructBST(root,i);
i=11;
root=constructBST(root,i);
commonParent=findCommonParent(root,node1,node2);
printf("\n The common parent is %d \n",commonParent->data);
return 0;
}
Since we are not allowed to store the nodes in a DS, the first thing that comes to my mind is the traversals. We can find the common root from two traversals.
Construct the preorder and inorder traversals. The common root is the one which has the follg two properties:
a) Should be present in between the two nodes in the inorder traversal
b) If there is more than one in a), then the common root is the one which occurs the left-most in the pre-order traversal.
We need not store the nodes per se in the DS but just their values from the traversals in say a array/vector...I believe thats allowed...
How about this- travel along the path from one of the 2 nodes to the root, and check each time if the other node occurs in the other subtree, i.e., if current node is left child, check the right child subtree or vice-versa.
Let the nodes be (a,b)
findLca( Node *a, Node *b )
{
bool found = false;
Node *p = findParentOf( a );
//try finding b in the tree rooted at p->left
if ( findNodeIn( b, p->left ) ) {
return p;
}
Node *otherSubTree = p->right;
// the other node has to be in otherSubTree
// or a subtree of an ancestor of p, unless
// the other node is p itself, in which case
// return its parent
while ( 1 ) {
if ( findNodeIn( b, otherSubTree ) ) {
return p;
}
// Here we know LCA is either p or
// in a subtree of p's ancestor
Node *newP = findParentOf( p );
if ( !newP || p == b ) {
return newP;
}
if ( p == newP->left ) {
otherSubTree = newP->right;
}
else {
otherSubTree = newP->left;
}
p = newP;
}
}
Why do people get carried away and give all kind of weirdo answers! and half of the page long codes dont make any sense without description. Please avoid doing that.
Coming to the problem. We know that root is not given and it is not a BST. But one thing is that it has pointer to the parent.
*This problem is similar to finding the intersection of two linked lists*.
Now use the same logic of finding the intersection of two linked lists here and find it. you would get it.
node* LCA(node* root, int a, int b)
{
if (!root || root->data == a || root->data == b)
return NULL;
node* lcaNode = NULL;
int tmp = findLCA(root, a, b, &lcaNode);
return lcaNode;
}
int findLCA(node* root, int a, int b, node** lcaNode)
{
if (!root)
return 0;
int l = findLCA(root->left, a, b, lcaNode);
int r = findLCA(root->right, a, b, lcaNode);
if (l + r == 2)
{
if (*lcaNode == NULL)
{
*lcaNode = root;
}
return 2;
}
else
{
return l + r + ((root->data == a) || (root->data == b) ? 1 : 0);
}
}
Properties:
1. Binary tree. not necessarily BST.
2. No parent node;
---code---
class Ancestor{
static Node leftNode,rightNode;
static String leftCode,rightCode;
static private void inorderTraversal(Node n, String code){
if(n==leftNode)
leftCode=code;
if(n==rightNode)
rightCode=code;
if(n.left!=null)
inorderTraversal(n.left,code + "0");
if(n.right!=null)
inorderTraversal(n.right,code + "1");
}
static public Node findCommonAncestor(Node root, Node left, Node right){
leftNode=left; rightNode=right;
inorderTraversal(root,""); //empty string
Nodeparent=root;
for(int i=0;i<leftCode.length&&i<rightCode.length;i++)
{
if(leftCode.charAt(i)!=rightCode.charAt(i))
break;
else{
if(leftCode.charAt(i)=='0')
parent = parent. left;
else
parent = parent. right;
}
}
if(i==leftCode.size()||i==rightCode.size())
return null;
else
return parent;
}
}
int commonparent(struct node *node,struct node *one,struct node *two,int*cparent)
{
int i,j;
if(node==NULL)
return 0;
i=commonparent(node->left,one,two,cparent);
j=commonparent(node->right,one,two,cparent);
if(node==one || node==two)
return 1;
if(i & j)
{
*cparent=node->data;
}
if(node==one)
return *cparent;
return(i | j);
}
if we have the parent link of each node, it's easy. the code is as following:
private treenode findCommonAncestor(treenode n1, treenode n2){
if(n1.parent.data == n2.parent.data)
return n1.parent;
return null;
}
But the pre-condition is that we don't have link to parent and the tree is not BST.
class TreeNode
{
public TreeNode Right;
public TreeNode Left;
public TreeNode Parent;
public int key;
}
static TreeNode FindNode(TreeNode root, int key)
{
TreeNode RetNode = null;
if (root == null)
{
return null;
}
if (root.key == key)
{
return root;
}
RetNode = FindNode(root.Left, key);
if (RetNode == null)
{
RetNode = FindNode(root.Right, key);
}
return RetNode;
}
static TreeNode FindCommonParent(TreeNode root, int nodeKey1, int nodeKey2)
{
if (root == null) return null;
if (root.key == nodeKey1) return FindNode(root, nodeKey1);
if (root.key == nodeKey2) return FindNode(root, nodeKey2);
int hieght1 = 0;
int hieght2 = 0;
TreeNode node1 = FindNode(root, nodeKey1);
TreeNode node2 = FindNode(root, nodeKey2);
if (node1 == null || node2 == null) return null;
TreeNode Cur1 = node1;
TreeNode Cur2 = node2;
while (Cur1.Parent != null)
{
hieght1++;
Cur1 = Cur1.Parent;
}
while (Cur2.Parent != null)
{
hieght2++;
Cur2 = Cur2.Parent;
}
Cur1 = node1;
Cur2 = node2;
if (hieght1 > hieght2)
{
int diff = hieght1 - hieght2;
while (diff-- != 0)
{
Cur1 = Cur1.Parent;
}
}
else if (hieght1 < hieght2)
{
int diff = hieght2 - hieght1;
while (diff-- != 0)
{
Cur2 = Cur2.Parent;
}
}
while(Cur1.Parent != null && Cur2.Parent != null)
{
if (Cur1.Parent == Cur2.Parent)
{
return Cur1.Parent;
}
Cur1 = Cur1.Parent;
Cur2 = Cur2.Parent;
}
return Cur1.Parent;
}
}
bool NodeInTree(TreeNode* root, TreeNode* given)
{
if (!root || !given)
return false;
if (root == given)
return true;
bool found = (root->left ? NodeInTree(root->left, given) : false);
return found ? true : (root->right ? NodeInTree(root->right, given) : false);
}
TreeNode* FirstCommonAncestor_Rec_Core
(TreeNode* root, TreeNode* given1, TreeNode* given2)
{
if (!root)
return NULL;
if (root->left == given1 && root->left == given2 ||
root->right == given2 && root->right == given2)
return root;
if (NodeInTree(root->left, given1) && NodeInTree(root->right, given2) ||
NodeInTree(root->left, given2) && NodeInTree(root->right, given1))
return root;
TreeNode* fca = FirstCommonAncestor_Rec_Core(root->left, given1, given2);
return fca ? fca : FirstCommonAncestor_Rec_Core(root->right, given1, given2);
}
TreeNode* FirstCommonAncestor_Rec
(TreeNode* root, TreeNode* given1, TreeNode* given2)
{
if (!root || !given1 || !given2 ||
root == given1 || root == given2)
return NULL;
if (!NodeInTree(root, given1) ||
!NodeInTree(root, given2))
return NULL;
// This following is covered in Core
// if (given1 == given2)
return FirstCommonAncestor_Rec_Core(root, given1, given2);
}
Node commonPappa(Node root, Node n1, Node n2) {
if(root == null) {
return null;
}
char noexist = '';
char n1Pos = (isExists(root.left,n1)?'l': ((isExists(root.right,n1)?'r':noexist);
char n2Pos = (isExists(root.left,n2)?'l': ((isExists(root.right,n2)?'r':noexist);
if(n1Pos == noexist || n2Pos == noexist) {
return null;
}
if(n1Pos != n2Pos) {
return root;
}
else if(n1Pos == 'r') {
return commonPappa(root.right,n1,n2);
}
else {
return commonPappa(root.left,n1,n2);
}
}
boolean isExists(Node root, Node n) {
boolean flag;
if(root == n) {
return true;
}
if(isExist(root.left,n) {
return true;
}
else {
return isExist(root.right,n);
}
}
node* LCA(node* root, node* nd1, node* nd2){
if(root==NULL)
return NULL;
if(root->left==nd1 || root->right==nd1 || root->left==nd2 || root->right==nd2)
return root;
node* lc = LCA(root->left,nd1,nd2);
node* rc = LCA(root->right,nd1,nd2);
if(lc!=NULL && rc!=NULL)
return root;
if(lc==NULL) return rc;
else return lc;
}
sorry it should have been ...
node* LCA(node* nd, node* nd1, node* nd2){
if(nd==NULL)
return NULL;
if(nd->left==nd1 || nd->right==nd1 || nd->left==nd2 || nd->right==nd2)
return nd;
node* lc = LCA(nd->left,nd1,nd2);
node* rc = LCA(nd->right,nd1,nd2);
if(lc!=NULL && rc!=NULL)
return nd;
if(lc==NULL) return rc;
else return lc;
}
and call
node* parent = LCA(root, nd1, nd2);
This is not correct. Suppose you want to find the LCA of the root and another node. Can your program return the right answer?
this is not correct, assume that it stops at the root node. root->l == d1, but you might not find d2 in the right subtree of root.
"if(nd->left==nd1 || nd->right==nd1 || nd->left==nd2 || nd->right==nd2) return nd;"
search(node* root, node* d1, node* d2) {
node1 = searchR(root->l, d1, d2);
node2 = searchR(root->r, d1, d2);
if (node1 && node2) { pirnt root;}
}
node* searchR(node* root, node* d1, node* d2) {
if (root == 0) {return 0;}
if (root == d1 || root == d2) return root;
node1 = searchR(root->l, d1, d2);
node2 = searchR(root->r, d1, d2);
if ( node1 && node2) {print root; return root;}
else if (node1 != 0) {return node1;}
else {return node2;}
}
is the node typical sturcuture with left and right? or some other representation?
- king_k July 09, 2008