Adobe Interview Question Software Engineer / Developers
Country: India
Let x and y be the elements whose lowest common ancestor we want
First do inorder traversal of the binary tree, store in a list A
Second, do post order traversal of binary tree , store in list B
Find all the numbers in A which are between x and y and call the list C
Find their rank in B, which ever number in C comes last in B is the lowest common ancestor of x and y.
Correctness
List A contains ancestors of x and y and only one common ancestor, which is the lowest common ancestor.
There is only one common ancestor, because in binary tree inorder we traverse left , root , right hence between two elements x and y the root of sub tree is lowest common ancestor.
we use post order to find that node as in post order root is visited last
To understand this solution you can take a look at
youtube.com/watch?v=LFjCr2yDJdc
I guess it will fail in case both the nodes are leftmost nodes. Please correct me if i am wrong.
One change: Find all the numbers in A which are between x and y (including x and y) and call the list C
What you are suggesting will result in visiting every node twice. and also an extra memory is required for inorder and preorder.
what i propose is
LCA_BT(struct node *root,struct node *p,struct node *q)
{
struct node * left,*right;
if(root==NULL)
return root;
if(root== p or root ==q)
return root;
left=LCA_BT(root->left,p,q);
right=LCA_BT(root->right,p,q);
return (left?left:right);
}
Please do correct me if i am wrong...
if both left and right are non-empty then return the root.
So, you should add before your return statement,
if (left && right) return root ;
A Bottom-up Approach (Worst case O(n) ):
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in L&R subtrees
}
1.Take level order of the tree.
2.move the pointers p & q whose lca is to be found towards their parents,where both of them meet is the lca.
level order traversal O(n)
finding p & q in the queue O(n)
now NCA:
parentp=parent(p);
parentq=parent(q);
while(parentp!=paerntq)
{
if(parentp!=parentq)
p=parentp;
else
q=parentq;
parentp=parent(p);
parentq=parent(q);
}
return queue[parentp];
}
time complexity on whole=O(n)
space : large amount
I'm thinking of a similar algorithm to yours. First, find the level of p and q by continuously performing p = p.parent, q = q.parent until they hit the root (I assume we are given the pointers to p and q). So we can get the level of p & q (say Lp, Lq) in O(logn) time.
Then, if Lp > Lq, perform p = p.parent Lp-Lq times to make p and q at the same level (similarly if Lq > Lp). After this, we can set a while loop and let p = p.parent and q = q.parent "simultaneously" in each iteration, until they hit the same node, which is the lca.
The time complexity will be O(logn) without no extra space used. Do you think this algorithm is gonna work?
=========
Note that p and q must locate at the two different branches of the lca, so for BST, we just do the following:
Node n = root;
if(p.value > n.value && q.value > n.value) // assume distinct elements
n = n.right;
else if (p.value < n.value && q.value < n.value)
n = n.left;
else
return n;
//C code to find Least Common Ancestor
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *newNode(int data)
{
struct node *n=(struct node *)malloc(sizeof(struct node));
n->data=data;
n->left=NULL;
n->right=NULL;
return n;
}
int covers(struct node *root,struct node *p)
{
if(root==NULL)
return 0;
else if(root==p)
return 1;
else
return (covers(root->left,p) || covers(root->right,p));
}
struct node * LCA(struct node *root,struct node *p,struct node *q)
{
if(covers(root->left,p) && covers(root->left,q))
return LCA(root->left,p,q);
if(covers(root->right,p) && covers(root->right,q))
return LCA(root->right,p,q);
return root;
}
int main()
{
struct node *root=newNode(12);
root->left=newNode(20);
root->right=newNode(24);
root->left->left=newNode(11);
root->left->right=newNode(10);
root->left->right->right=newNode(8);
struct node *ans=LCA(root,root->left->left,root->left->right->right);
printf("The LCA is %d\n",ans->data);
return 0;
}
Step1:- first do preorder travsal,take a array which have the nodes value before first node seen;
Step 2:- do the postorder travsals,tke another arrey which have the nodes value after both node seen ...
Step3- take intersection of both arrey,,,,,after that the node whose value is lowest is the lowest ancestor of given binary tree....
Ex..two node 17 and 5 whose lowest ancestor 10
/ \
15 12
/ \
13 14
/ \ / \
17 18 11 5
/ \
20 21
preorder: 10,15,13,17,18,20,21,14,11,5
a[]={10,15,13}
postorder: 17,20,21,18,13,11,5,14,15,12,10
b[]={ 14,15,12,10}
intersection is { 10,15}
lowest is 10
so ans is 10...
Algorithmic complexity O(n)
Correct me if I am wrong on a case
//using the fact that it is BT and not BST
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <list>
using namespace std;
typedef struct node snode;
struct node
{
int data;
struct node *left, *right;
};
// helper function to allocate new node with given data
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = node->right = NULL;
return (node);
}
//maintain two lists
list<snode *> s1,s2;
//function to search the data for existance
int searchData(snode *root,int data,int mode){
//null node base
if(root==NULL){
return -1;
}
//data is in this node, hence return 1
if(root->data == data){
return 1;
}
//else look left and right for possibilities
//lf is left flag, rf is right flag
int lf,rf;
switch(mode){
//mode 1 for first num, mode 2 for second num
case 1:
if(root->left != NULL){
//first push this node
s1.push_back(root->left);
//then search
lf=searchData(root->left,data,mode);
//since it is found then return 1 flag
if(lf==1){
return 1;
}
//else revert the list to the old state
s1.pop_back();
}
if(root->right!=NULL){
//first push this node
s1.push_back(root->right);
//then search
rf=searchData(root->right,data,mode);
//since it is found then return 1 flag
if(rf==1){
return 1;
}
//else revert the list to the old state
s1.pop_back();
}
break;
case 2:
if(root->left != NULL){
s2.push_back(root->left);
lf=searchData(root->left,data,mode);
if(lf==1){
return 1;
}
s2.pop_back();
}
if(root->right!=NULL){
s2.push_back(root->right);
rf=searchData(root->right,data,mode);
if(rf==1){
return 1;
}
s2.pop_back();
}
break;
}
return -1; //to be safe
}
#define debugStates
void monitorLCA(snode * root,int data1,int data2){
int lf,rf;
//initialize the lists with the root
s1.push_back(root);
s2.push_back(root);
//search entries
lf = searchData(root,data1,1);
rf = searchData(root,data2,2);
#ifdef debugStates
//DEBUG control
cout<<"lf is "<<lf<<", rf is "<<rf<<endl;
//contents display
for(list<snode *>::iterator it=s1.begin();it!=s1.end();++it){
cout<<(*it)->data<<" ";
}
cout<<endl;
//contents display
for(list<snode *>::iterator it=s2.begin();it!=s2.end();++it){
cout<<(*it)->data<<" ";
}
cout<<endl;
#endif // debugStates
if(lf==-1 || rf==-1){
cout<<"data invalid"<<endl;
return;
}
//now maintain the last matched node and start popping
snode * last;
while((s1.front())->data == (s2.front())->data){
last = s1.front();
s1.pop_front();
s2.pop_front();
}
//display answer
cout<<"the lca was "<<(last->data)<<endl;
}
//DRIVER
int main(){
snode * root = newNode(5);
root->left = newNode(3);
root->left->left=newNode(1);
root->left->right=newNode(6);
root->right=newNode(2);
root->right->left=newNode(9);
root->right->right=newNode(8);
monitorLCA(root,100,6);
return 0;
}
C++ 11
1. Traverse tree until you find one of the nodes. While doing that collect the nodes in the path whose right tree you haven't traversed yet.
2. Search each node's right subtree of the nodes found in the above to check if it contains the other node. The first one that passes this test is the lowest common ancestor.
shared_ptr<vector<shared_ptr<TreeNode>>> FindPath(shared_ptr<TreeNode> t, shared_ptr<TreeNode> n1, shared_ptr<TreeNode> n2) {
if(t == nullptr) {
return nullptr;
}
if( t == n1 || t == n2) {
auto path = make_shared<vector<shared_ptr<TreeNode>>>();
path->push_back(t);
return path;
}
else {
if(t->left) {
auto path = FindPath(t->left, n1, n2);
if(path) {
if(t->right) {
path->push_back(t);
}
return path;
}
}
if(t->right) {
auto path = FindPath(t->right, n1, n2);
if(path) {
return path;
}
}
}
}
bool TreeContains(shared_ptr<TreeNode> t, shared_ptr<TreeNode> n) {
if(t == nullptr) {
return false;
}
if( t == n) {
return true;
}
return TreeContains(t->left, n) || TreeContains(t->right, n);
}
shared_ptr<TreeNode> FirstCommonAncestor(shared_ptr<TreeNode> t, shared_ptr<TreeNode> n1, shared_ptr<TreeNode> n2) {
auto path = FindPath(t, n1, n2);
auto path_length = path->size();
if(path_length > 0) {
auto other_node = path->at(0) == n1 ? n2 : n1;
if(TreeContains(path->at(0), other_node)) {
return path->at(0);
}
for(int i = 1; i < path_length; i++) {
if(TreeContains(path->at(i)->right, other_node)) {
return path->at(i);
}
}
} else {
return nullptr;
}
}
BST does provide us information which helps us to do better than a normal binary tree code...we can know at first whether to go to the right child or the left child accordingly whereas in binary tree we have to consider all the possibilities of the right child as well as left child of the root to find the LCA.
- kavish dwivedi August 26, 2012