Amazon Interview Question
InternsCountry: United States
Interview Type: Phone Interview
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *left;
struct node *right;
};
struct node * newNode(int data){
struct node * root = (struct node *)malloc(sizeof(struct node));
root->data = data;
root->left = NULL;
root->right = NULL;
return root;
}
int findPath(struct node *root, int value,int * a,int i){
if(root==NULL){
return 0;
}
if(root->data == value || findPath(root->left,value,a,i+1)||findPath(root->right,value,a,i+1)){
a[i] = root->data;
return i;
}
return 0;
}
int findAncestor(int a[],int b[],int i,int prev){
if(a[i] == b[i]){
prev = findAncestor(a,b,i+1,a[i]);
return prev;
}
else{
return prev;
}
}
int main(){
struct node * root;
int i =0,index1=0,index2=0;
int path1[100];
int path2[100];
memset(path1,-1,sizeof(path1));
memset(path1,-1,sizeof(path2));
root= newNode(17);
root->left = newNode(12);
root->right = newNode(13);
root->right->left = newNode(9);
root->right->left->left = newNode(5);
root->right->left->left->left = newNode(1);
root->right->right = newNode(3);
root->right->right->right = newNode(2);
root->right->right->right->right = newNode(8);
index1= findPath(root,1,path1,0);
index2= findPath(root,8,path2,0);
printf("%d",findAncestor(path1,path2,0,-1));
getch();
}
1. Do an inorder and post order traversal
2. find position of both elements in inorder array and note the range.
3. now find rank of all elements from this range in post order array.
4. last ranked element in post order is lowest common ancestor.
an O(N) solution wrt time complexity.
Define your terms a little bit more I looked on wikipedia for Binary tree and I see the Distinction from the common BST but it does not mention a lowest common ancestor
How about "finding the node with largest depth such that it is the root of a subtree that contains both of the specified nodes"?
I would say the answer lies in bubbling up from both nodes simaltaneously checking each step to see if they have reached there common ancestor
in dt case! the nodes cud be at diff heights! so i don think bubbling up wud be a good idea!
Assumptions:
I'm printing the common ancestor.
II'm given a TreeNode structure that has a left and right pointer.
data is an int
a is 1000
b is 1
int common( TreeNode* root, int a, int b ){
if ( root == null ) return 0;
int leftCount = common(root->left, a, b);
int rightCount = common(root->right, a,b);
int mine;
// can't be both, right?
mine = ( root->data == a )? 1000: 0;
mine = ( root->data == b )? 1: 0;
// found already deeper in the tree
if ( leftCount == 1001 || rightCount == 1001) return 1001;
// nothing in my children, return my count
if ( leftCount == rightCount == 0 ) return mine;
// if we are here, the checks above arent true
// so check if we found something
if ( (leftCount + rightCount == 1001)
|| (mine + leftCount + rightCount == 1001) ){
// print
std::cout << "Here: " << root->data << std::endl;
// found
return 1001;
}
// left and right children doesnt have a AND b, so we're here
// possible they have either one though,
// mine isn't a or b so return children count
if ( mine == 0 && (leftCount != rightCount) )
return leftCount+rightCount ;
// both children had the same node data ( both a or both b)
else if( mine == 0 && leftCount == rightCount ) return leftCount;
// if I have same data as one of my children
// just return their count
else if ( mine == leftCount ) return leftCount ;
else if( mine == rightCount ) return rightCount ;
return mine;
}
class TreeNode {
int val;
TreeNode leftchild;
TreeNode rightchild;
}
public class Solution {
public static TreeNode findCommonAncestor(TreeNode root, TreeNode a, TreeNode b) {
if (root == null || a == null || b == null) {
return null;
}
TreeNode ret = null;
traverse(root, a, b, ret);
return ret;
}
public static int traverse(TreeNode root, TreeNode a, TreeNode b, TreeNode ret) {
if (root == null) {
return 0;
}
if (root == a || root == b) {
return 1;
}
int value = traverse(root.leftchild, a, b, ret)+traverse(root.rightchild, a, b, ret);
if (value == 2) {
ret = root;
return 3;
}
else {
return value;
}
}
}
NodeType* lowest(NodeType* root,NodeType* p,NodeType*q){
if(root==NULL)return NULL;
if(root==p||root==q)return root;
NodeType* left=lowest(root->left,p,q);
NodeType* right=lowest(root->right,p,q);
if(left!=NULL||right!=NULL)return root;
if(left!=NULL)return left;
if(right!=NULL)return right;
return NULL;
}
Step1: traverse postorder ex:8,2,5,25,19,21,15,17,29,20,10,40,50,30,9
Step2: traverse preorder ex:9,10,15,5,8,2,21,25,19,20,17,29,30,40,50
Step 3: if our two node 8 and 19 then in postorder the element after 19 ...21,15,17,29,20,10,40,50,30,9 and the elemnet before 8 in preorder 9,10,15,5
step 4: find the commen element in both ex. 9,10,15
Step 5: find the min in this arrey ex. from 9,10,15 is 9 so lowest commen ancester is 9.
Ex our tree is 9
10 / \30
15 / \ 20 40/ \ 50
5/ \ 21 17 / \29
8/ \2 25/ \19
public Node findAncestor(Node n, Node m){
if(n == null || m == null) return null;
Set<Node> nodeSet = new HashSet<Node>();
while(n!=null || m!=null){
if(n!=null && !nodeSet.contains(n.parent)){
nodeSet.add(n.parent);
n = n.parent;
}else{
return n.parent;
}
if(m!=null && !nodeSet.contains(m.parent)){
nodeSet.add(m.parent);
m = m.parent;
}else{
return m.parent;
}
}
return null;
}
#include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef struct treeNode* treeNodePtr; struct treeNode{ int data; treeNodePtr left; treeNodePtr right; }; treeNodePtr findLCA(treeNodePtr root, int p, int q) { // no root no LCA. if(!root) { return NULL; } // if either p or q are direct child of root then root is LCA. if(root->data==p || root->data==q) { return root; } else { // get LCA of p and q in left subtree. treeNodePtr l=findLCA(root->left , p , q); // get LCA of p and q in right subtree. treeNodePtr r=findLCA(root->right , p, q); // if one of p or q is in leftsubtree and other is in right // then root it the LCA. if(l && r) { return root; } // else if l is not null, l is LCA. else if(l) { return l; } else { return r; } } } treeNodePtr newNode(int data) { treeNodePtr newNode = malloc(sizeof(struct treeNode)); if(!newNode) { fprintf(stderr,"Error allocating memory\n"); exit(1); } newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } int main() { /* 5 / \ 7 6 /\ /\ 1 2 3 4 /\ 0 8 */ treeNodePtr root = newNode(5); treeNodePtr tmp; root->left = newNode(7); root->right = newNode(6); root->left->left = newNode(1); root->left->right = newNode(2); root->right->left = newNode(3); root->right->right = newNode(4); root->left->left->left = newNode(0); root->left->left->right = newNode(8); int arr[] = {0,1,2,3,4,5,6,7,8}; int size = sizeof(arr)/sizeof(*arr); int i,j; for(i=0;i<size;i++) { for(j=i+1;j<size;j++) { tmp = findLCA(root,arr[i],arr[j]); printf("LCA of %d %d is %d\n",arr[i],arr[j],tmp->data); } } return 0; }
#include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef struct treeNode* treeNodePtr; struct treeNode{ int data; treeNodePtr left; treeNodePtr right; }; treeNodePtr findLCA(treeNodePtr root, int p, int q) { // no root no LCA. if(!root) { return NULL; } // if either p or q are direct child of root then root is LCA. if(root->data==p || root->data==q) { return root; } else { // get LCA of p and q in left subtree. treeNodePtr l=findLCA(root->left , p , q); // get LCA of p and q in right subtree. treeNodePtr r=findLCA(root->right , p, q); // if one of p or q is in leftsubtree and other is in right // then root it the LCA. if(l && r) { return root; } // else if l is not null, l is LCA. else if(l) { return l; } else { return r; } } } treeNodePtr newNode(int data) { treeNodePtr newNode = malloc(sizeof(struct treeNode)); if(!newNode) { fprintf(stderr,"Error allocating memory\n"); exit(1); } newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } int main() { /* 5 / \ 7 6 /\ /\ 1 2 3 4 /\ 0 8 */ treeNodePtr root = newNode(5); treeNodePtr tmp; root->left = newNode(7); root->right = newNode(6); root->left->left = newNode(1); root->left->right = newNode(2); root->right->left = newNode(3); root->right->right = newNode(4); root->left->left->left = newNode(0); root->left->left->right = newNode(8); int arr[] = {0,1,2,3,4,5,6,7,8}; int size = sizeof(arr)/sizeof(*arr); int i,j; for(i=0;i<size;i++) { for(j=i+1;j<size;j++) { tmp = findLCA(root,arr[i],arr[j]); printf("LCA of %d %d is %d\n",arr[i],arr[j],tmp->data); } } return 0; }
bool lca(const T &a, const T &b, T &result, std::function<int(const T &, const T &)> compare) {
Node *popNode;
Stack<Node *> stack;
std::vector<const T *> elements = { &a, &b };
std::function<bool(Node *)> findNode;
findNode = [&](Node *node) -> bool {
if (!node)
return false;
if (elements.size() == 2)
stack.push(node);
auto it = elements.begin();
while (it != elements.end()) {
if (compare(node->m_data, *(*it)) == 0) {
elements.erase(it);
stack.pop(popNode);
if (popNode != node)
stack.push(popNode);
return true;
}
else
++it;
}
if (findNode(node->m_left) && elements.empty())
return true;
if (findNode(node->m_right) && elements.empty())
return true;
stack.pop(popNode);
if (popNode != node)
stack.push(popNode);
return false;
};
struct Node *node;
if (findNode(m_root) && stack.pop(node)) {
result = node->m_data;
return true;
}
return false;
}
This is a question straight out of cracking the coding Interview..
- Ankush February 22, 2013