Microsoft Interview Question Software Engineer / Developers
It is possible to solve this without building additional queues. The system stack is actually your queue.
Your recursive traverse function must return true if one of the nodes is found, and each instance of this function should pass this result up to the previous callers. The common ancestor is the node that receives true from both left and right branches.
Hi,
if u have O(n) space one can do it in O(n) run time
traverse preorder the addresses of the nodes and store it.
then traverse inorder the addresses of the nodes and store it.
eg tree
a
b c
d e f
have PreOrder:a b d e c f
Inorder: d b e a c f
for two node ptrs eg d and c
mark the positions in inorder array and find first preorder ptr which seprates it into two
different parts of Inorder array
for above example first preorder ptr is a which seprates inorder into dbe and cf
so a is first commom ancester of d and c
rpandey@cdotd.ernet.in
Can be solved in O(logn) space and O(n) time
1. Do DFS
2. During DFS, if you find one of the nodes, store the stack contents(path from the root). Repeat for both nodes. This requires 2logn space
3. Now compare both these paths from root.. the last common node in the path is the first common ancestor. This takes 'logn' time in avg case and 'n' in worst case.
The lowest common ancestor's key value will be in between the two given numbers. Return the first node of this kind you encounter.
The following code will work only if the 2 given nodes in the problem exist in the tree.
typedef struct _node{
int data;
struct node *left;
struct node *right;
} node;
//here num1 and num2 are two given nodes' values whose lowest common //ancestor needs to be found
void* lowestCommonAncestor(node *root,int num1,int num2){
if(root==NULL)
return NULL;
if(root->right == NULL || root->left == NULL)
return NULL;
node *curnode;
curnode = root;
while(curnode){
if(num1 < curnode->data && num2 < curnode->data){
curnode=curnode->left;
}
else if(num1 > curnode->data && num2 > curnode->data){
curnode=curnode->right;
}
else if(num1<curnode->data && num2>curnode->data){
return curnode;
}
}
}
Raman, are u suggesting to do the following?
look at the curNode
If node1->data and node2->data are less than the curNode->data
go to the the left child
If node1->data and node2->data are greater than the curNode->data
go to the right child
Otherwise
The curNode is the lowest common ancestor
You can assign a dewy ID to each node as you scan the tree and then find the common substring between the deweyIDs for the two leaves given. That will give the LCA. Another approach is to label all the nodes based on the level and then find the Euler tour and then determine the LCA. The following link should be useful....
coursesdotcsaildotmitdotedu/6dot897/spring03/scribe_notes/L11/lecture11dotpdf
1. look for the parent of node1 and node2 , if they are equal then we found the common ancestor other assign the parent value to nodes and start iterating again and till do untill node1 or node2 is not null.
that can be done in O(n) ways and O(1) space complexity
FindCommonAncestor( struct tree *node1 , struct tree *node2, struct tree *common )
{
common = NULL;
while( node1 |= NULL || node2 != NULL )
{
if( node1->parent == node2->parent )
{
common = node1->parent;
break;
}
else
{
node1 = node1->parent;
node2 = node2->parent;
}
}
}
nope, man...
first, it's not said that tree structure has 'parent' pointers,
second, your solution only works if leaf nodes have the same depth (which is not true even if the tree were balanced).
here is a simple recursive solution:
node *p1, *p2;
node *common = 0;
bool common_ancestor(node *t) {
if(t == 0)
return false;
if(t == p1 || t == p2) // match found
return true;
bool hit1 = common_ancestor(t->left);
if(common != 0) // already found
return false;
bool hit2 = common_ancestor(t->right);
if(hit1 & hit2) {
common = t;
return false;
}
return (hit1 | hit2);
}
main() {
// assign p1 and p2 to some leaf nodes
common_ancestor(root);
}
Tested. Use two vectors to record the path to 2 nodes:
==============================================================
bool findPath(Node* root, Node* node, vector<Node*>& v)
{
..if (root==NULL)
....return false;
..else if (root==node){
....v.push_back(root);
....return true;
..}
..else if(findPath(root->left, node, v)||findPath(root->right, node, v)){
....v.push_back(root);
....return true;
..}
..else return false;
}
int main()
{
..Tree tree;
..Node* root=tree.createTree();
..Node* node1=root->left->right;
..Node* node2=root->right->left;
..Node* common;
..vector<Node*> v1, v2;
..findPath(root, node1, v1);
..findPath(root, node2, v2);
..while (v1.back()==v2.back()){
....common=v1.back();
....v1.pop_back();
....v2.pop_back();
..}
..cout<<common->value;
..tree.deleteTree();
}
Test passed. Recursion version:
===========================================================
bool postOrder(Node* root, Node* node1, Node* node2, Node** common)
{
..if (root==NULL)
....return false;
..//node1 or node2 is current root
...bool isSelf=(root==node1)||(root==node2);
..//left branch of current root has one node;
..bool left= postOrder(root->left, node1, node2, common);
..//right branch of current root has one node;
..bool right=postOrder(root->right, node1, node2, common);
..//case1: node1 and node2 are the same node
..if (node1==node2){
....*common=node1;
....return true;
..}
..//case2: (left && right): node1 and node2 are one left and right branches of root
..//case3: (isSelf&&left): root is one node, and another node is on the left branch
..//case4: (isSelf&&right): root is one node, and another node is on the right branch
..if ((left && right) || (isSelf&&left) || (isSelf&&right)){
....*common=root;
....return true;
..}
..//only one node is detected:
..else if (left || right || isSelf)
....return true;
..//neither node1 nor node2 is detected:
..else
....return false;
}
int main()
{
..Tree tree;
..Node* root=tree.createTree();
..Node* node1=root->left->left;
..Node* node2=root->left;
..Node** common=&root;
..postOrder(root, node1, node2, common);
..tree.deleteTree();
}
Using Node*& instead of Node** as parameter common
======================================
bool postOrder(Node* root, Node* node1, Node* node2, Node*& common)
{
..if (root==NULL)
....return false;
..bool isSelf=(root==node1)||(root==node2);
..bool left= postOrder(root->left, node1, node2, common);
..bool right=postOrder(root->right, node1, node2, common);
..if (node1==node2){
....common=node1;
....return true;
..}
..if ((left && right) || (isSelf&&left) || (isSelf&&right)){
....common=root;
....return true;
..}
..else if (left || right || isSelf)
....return true;
..else
....return false;
}
int main()
{
..Tree tree;
..Node* root=tree.createTree();
..Node* node1=root->left->left;
..Node* node2=root->left;
..Node*& common1=root;
..postOrder(root, node1, node2, common1);
..tree.deleteTree();
}
working code
#include<iostream>
#include <vector>
#include <algorithm>
struct node {
int value;
struct node *left;
struct node *right;
node(int a) {
value = a;
left = NULL;
right = NULL;
}
};
node *createBST(std::vector<int> numbers, int low, int high) {
// create tree from numbers
if (low > high) return NULL;
int mid = (low + high) / 2;
node *root = new node(numbers[mid]);
root->left = createBST(numbers, low, mid -1);
root->right = createBST(numbers, mid+1, high);
return root;
}
void printHeight(node* root) {
static int height = 0;
height++;
if(root == NULL) {
height--;
return;
}
printHeight(root->left);
for(int i = 1; i <= height; i++)
std::cout << "\t";
std::cout << root->value << "\n";
printHeight(root->right);
height--;
}
bool isInSubTree(const struct node* root, int val) {
if(root == NULL) {
return false;
}
if(root->value == val) return true;
return (isInSubTree(root->left, val) || isInSubTree(root->right, val));
}
node * findCommonAncestor(struct node* root, int first, int second) {
if(root == NULL) {
return NULL;
}
if((isInSubTree(root->left, first) && isInSubTree(root->right, second)) ||
(isInSubTree(root->left, second) && isInSubTree(root->right, first))) {
return root;
}
if(isInSubTree(root->left, first) && isInSubTree(root->left, second)) {
return findCommonAncestor(root->left, first, second);
}
if(isInSubTree(root->right, first) && isInSubTree(root->right, second)) {
return findCommonAncestor(root->right, first, second);
}
}
int main() {
std::cout << "Enter first and second\n";
int first;
int second;
std::cin >> first;
std::cin >> second;
std::vector<int> numbers;
int temp;
while(std::cin >> temp) {
numbers.push_back(temp);
}
std::sort(numbers.begin(), numbers.end());
node *root = createBST(numbers, 0, numbers.size() - 1);
printHeight(root);
std::cout << "\n";
node *commonAncestor = findCommonAncestor(root, first, second);
if (!commonAncestor) {
std::cout << "No common ancestor found";
} else {
std::cout << "Common ancestor is " << commonAncestor->value;
}
std::cout << "\n";
return 0;
}
A Java solution for this question. It is basically a post-order traversal of the input tree with some early cut-offs (proceeding if we already found the first common ancestor). Time O(n), Space O(1).
public class TreeNode
{
public TreeNode left=null;
public TreeNode right=null;
int val;
public TreeNode(int v)
{
val=v;
}
public String toString()
{
return String.format("[TreeNode: val=%d]", val);
}
public String toStringAll()
{
return String.format("[TreeNode: val=%d, left=%s, right=%s]", val,
(left!=null) ? left.toStringAll() : null,
(right!=null) ? right.toStringAll() : null);
}
}
public class ID2319
{
TreeNode ancestor=null;
boolean done=false;
public TreeNode firstCommonAncestor(TreeNode root, TreeNode leaf1, TreeNode leaf2)
{
if (root==null || leaf1==null || leaf2==null)
return null;
// initialize
ancestor=null;
done=false;
TreeNode result=firstCommonAncestorRecursive(root, leaf1, leaf2);
if (result==null || result==leaf1 || result==leaf2)
return null;
else
return result;
}
public TreeNode firstCommonAncestorRecursive(TreeNode root, TreeNode leaf1, TreeNode leaf2)
{// post-order traversal with early cut-offs
if (root==null || root==leaf1 || root==leaf2)
return root;
TreeNode left=firstCommonAncestorRecursive(root.left, leaf1, leaf2);
if (done)
return ancestor;
TreeNode right=firstCommonAncestorRecursive(root.right, leaf1, leaf2);
if (done)
return ancestor;
if (left==null)
return right;
else if (right==null)
return left;
else if (left!=null && right!=null)
{
if (ancestor==null)
{
ancestor=root;
done=true;
}
return ancestor;
}
return ancestor;
}
public static void main(String[] args)
{
TreeNode root=new TreeNode(1);
root.left=new TreeNode(2);
root.right=new TreeNode(3);
root.left.left=new TreeNode(4);
root.left.right=new TreeNode(5);
root.right.left=new TreeNode(6);
root.right.right=new TreeNode(7);
root.left.left.left=new TreeNode(8);
root.left.left.right=new TreeNode(9);
root.right.left.left=new TreeNode(10);
root.right.left.right=new TreeNode(11);
root.right.right.right=new TreeNode(12);
System.out.println(root.toStringAll());
ID2319 wpd=new ID2319();
System.out.println(wpd.firstCommonAncestor(root, root.left.left.right, root.right.right.right));
System.out.println(wpd.firstCommonAncestor(root, root.left.left.right, root.left.right));
System.out.println(wpd.firstCommonAncestor(root, root.left.left.right, new TreeNode(14)));
System.out.println(wpd.firstCommonAncestor(root, root.left.left.right, null));
}
}
Hi,
- Ravi Kant Pandey March 26, 2007if u have O(n) space you can do it in O(n) run time
traverse preorder the addresses of the nodes and store it.
then traverse inorder the addresses of the nodes and store it.
eg tree
a
b c
d e f
have PreOrder:a b d e c f
Inorder: d b e a c f
for two node ptrs eg d and c
mark the positions in inorder array and find first preorder ptr which seprates it into two
different parts of Inorder array
for above example first preorder ptr is a which seprates inorder into dbe and cf
so a is first commom ancester of d and c