Amazon Interview Question
Software Engineer in TestsTeam: Kindle
Country: United States
Interview Type: Phone Interview
Very nice. You don't really need R==null in the last if. You also can change R==null to !R and R!=null to just R, etc., because null evaluates to false.
It doesn't work if just one of the nodes is not in the tree. In that case it returns the node that is in the tree. But I think the original question allows the assumption that they are in the tree.
Simple but not elegant..
What if one of the input nodes is a child of another?
For example Say node *a is same as head and node *b exists somewhere in the left or right branches;
In that case "head == a" and so it will return the head as the LCA, which is correct.
The code is indeed quite clean, but can be a little confusing too because the method the intent of this recursive method is different between the main call and the recursive ones. The main call finds the LCA while the recursive one just finds whatever node is equal to "a" or "b". But no big deal.
Very simple solutiion ^^
int find_node2( Node *node, int value1, int value2 ) {
int ret = 0;
if( node->data == value1 || node->data == value2 ) {
ret++;
}
if( node->left ) {
ret += find_node2( node->left, value1, value2 );
}
if( node->right ) {
ret += find_node2( node->right, value1, value2 );
}
if( ret == 2 ){
printf("this node is common parent: %d(%d,%d)\n",
node->data, value1, value2);
}
return ret > 0 ? 1 : 0;
}
+1 Nice. Very minimal solution. This assumes data is an identifier, which I wasn't assuming, but should have. I like the return counter... slick!
Have you read the original question ? You have to find (and presumably return it) the LCA node, while your code just returns integers.
@ashot madatyan, yes it just returns integer, if it finds valid node, it is easy to return the node itself.
1. let A and B are the nodes
2. traverse from A to the root node using the parent link and hash each traversed node
3. traverse from B to the root node using the parent link and same time check in the hash table
4. if a node found in the hash table, that is the least commmon Ancestor
Here complexity is: T -> O(n) & S -> O(n) since it a binary tree.
strucy Node *tmp=root;
while(tmp!=NULL)
{
if(tmp->data > fisrtNode->data && tmp->data > secondNode->data)
tmp=tmp->leftChild;
else if(tmp->data < firstNode->data && tmp->data < secondNode->data)
tmp=tmp->rightChild;
else
{
if(firstNode->parent == secondNode)
return secondNode->parent;
else if(secondNode->parent == firstNode)
return firstNode->parent;
else
return tmp;
}
}
A slight variation I was given stated that the desired nodes might not be in the Binary Search Tree, and that duplicates values in the BST are allowed, and will be put on the left.
Let Node A and B the nodes in question.
1. Search for a Node A in the binary tree. Record a path to A as you search it.
2. Repeat above for Node B.
3. At this point you have a path from root to A and a path from root to B.
4. Search through these paths and find the least common nodes that appear in the paths.
Not sure if I am breaking rules of the asker with this solution. (I added params to track the parent as you look for the child)
class Program
{
static void Main(string[] args)
{
Node node5 = new Node(5, null, null);
Node node4 = new Node(4, null, null);
Node node3 = new Node(3, null, null);
Node node2 = new Node(2, node4, node5);
Node node1 = new Node(1, node2, node3);
Node common = NodeHelper.ParentFinder(node1, node4, node3);
Console.WriteLine(common.data);
Console.ReadLine();
}
}
class Node{
public int data;
public Node leftchild;
public Node rightchild;
public Node(int _data, Node _leftchild, Node _rightchild)
{
data = _data;
leftchild = _leftchild;
rightchild = _rightchild;
}
//adding some helper fields
public Node parent;
public int level;
}
static class NodeHelper
{
public static Node ParentFinder(Node root, Node node1, Node node2)
{
if (nodeParentPopulater(root, null, node1, 0) && nodeParentPopulater(root, null, node2, 0))
{
//continue
}
else
{
//nodes not found
return null;
}
Node temp1 = node1;
Node temp2 = node2;
//find each nodes parent node that lives at the same level
while (temp1.level > temp2.level)
{
temp1 = temp1.parent;
}
while (temp1.level < temp2.level)
{
temp2 = temp2.parent;
}
//now start checking if the nodes are the same
while (!temp1.Equals(temp2))
{
temp1 = temp1.parent;
temp2 = temp2.parent;
}
//parents are the same. return the parent node
return temp1;
}
private static bool nodeParentPopulater(Node node, Node parentNode, Node nodeToFind, int level)
{
bool found = false;
node.parent = parentNode;
node.level = level;
if (node.Equals(nodeToFind)) return true;
if (node.leftchild != null)
{
found = nodeParentPopulater(node.leftchild, node, nodeToFind, level + 1);
}
if (!found && node.rightchild != null)
{
found = nodeParentPopulater(node.rightchild, node, nodeToFind, level + 1);
}
return found;
}
}
Below is the code without using parent link
public class LCABT {
static BTNode lca = null;
static BTNode foundNode = null;
private static boolean findLCA(BTNode root,int a, int b, boolean inPath){
if(root == null)
return false;
if(root.getData() == a || root.getData() == b){
if(foundNode!=null && foundNode.getData()!=root.getData()){
if(inPath)
lca = foundNode;
return true;
}else{
foundNode = root;
inPath = true;
}
}
boolean inLeft = false;
boolean inRight = false;
if(lca == null)
inLeft = findLCA(root.getLeft(),a,b,inPath);
if(lca == null){
inRight = findLCA(root.getRight(),a,b,inPath);
if(lca==null && inLeft && inRight){
lca = root;
}
}
if(lca == null && root == foundNode){
inPath = false;
return true;
}
return inLeft || inRight;
}
public static void main(String[] argv){
BTNode n1 = new BTNode(5);
BTNode n2 = new BTNode(2);
BTNode n3 = new BTNode(3);
BTNode n4 = new BTNode(9);
BTNode n5 = new BTNode(11);
BTNode n6 = new BTNode(50);
BTNode n7 = new BTNode(7);
n1.setLeft(n2);
n1.setRight(n3);
n2.setLeft(n4);
n2.setRight(n5);
n3.setRight(n6);
n4.setLeft(n7);
findLCA(n1,11,7,false);
System.out.println("LCA : "+lca.getData());
}
}
class BTNode{
private int data;
private BTNode left;
private BTNode right;
public BTNode(int data){
this.setData(data);
}
public void setLeft(BTNode left) {
this.left = left;
}
public BTNode getLeft() {
return left;
}
public void setRight(BTNode right) {
this.right = right;
}
public BTNode getRight() {
return right;
}
public void setData(int data) {
this.data = data;
}
public int getData() {
return data;
}
}
The idea is to search for the nodes in the left sub tree and the right sub tree starting at the root. Recursive calls to the function FindCommonAncestorInBinaryTree() checks if the nodes are found. If one of nodes is found, it is marked as found and the search will continue for the next node. More explanation and code can be found here:
linearspacetime.blogspot.com/2012/04/find-common-ancestor-of-two-nodes-in.html
LCA of two nodes in a binary tree - complete implementation that also checks whether the nodes are in the tree at all. Algorithm description are inline, as well as inlined are the comments to help you understand the complete flow of the algo:
bool contains(Node *root, Node *sought)
{
if (NULL == root)
return false;
if (root->data == sought->data)
return true;
return (contains(root->left, sought) || contains(root->right, sought));
}
/**
Algorithm description:
Find the subtrees where the two nodes are contained.
if either of the nodes is not found
return NULL
else
return the node starting from where the two nodes being sought are in different subtrees (the two nodes diverge)
*/
Node* LCA (Node *root, Node *firstnode, Node *secondnode)
{
bool ffound_in_left, ffound_in_right, sfound_in_left, sfound_in_right;
ffound_in_left = contains(root->left, firstnode);
if (ffound_in_left) {
sfound_in_left = contains(root->left, secondnode);
if (sfound_in_left) {
return LCA(root->left, first, second);
}
else {
sfound_in_right = conatins(root->right, second);
if (sfound_in_right) // the nodes diverge here (the first is in the left and the second is in the right, so return root)
return root;
return NULL; // the right node has not been found at all
}
}
else { // the first node not in left, try to find it in the right subtree
ffound_in_right = contains(root->right, first);
if (ffound_in_right) {
sfound_in_right = contains(root->right, second);
if (sfound_in_right) {
return LCA(root->right, first, second); // both the first and second nodes are in the right subtree, go to there
}
else { // the first found in the right and the second not found in the right, check to see whether the second exists in the tree at all
sfound_in_left = contains(root->left, second);
if (sfound_in_left == true) { // second found in the left subtree, while the first is in the right, so they diverge
return root; //
}
else { // second not found in the tree at all
return NULL;
}
}
}
}
// first not found in the right subtree either, so it is not present in the tree at all
return NULL;
}
What does the contains function do? Depth first search?
Whats the time complexity of the contains function?
@CameronWills
The "contains" function is very straightforward - starting from the input node it just looks for the node with the given value. First it checks the input node's value, if it is not the one being sought, it looks in the left and then in the right subtrees of the given node.
Time complexity of this function is O(N). The overall time complexity of the given solution is quadratic, with constant space.
@sonny.c.patterson
Would you please bother yourself commenting the "Ugh" - for me this term does not contain any logic, neither does it provide us with any counterarguments or some constructive reasoning.
I stand by my comment. This is the most horrible piece of code imaginable. My children cried when they saw it. My dog ran into the road an threw himself under the first passing car. Jesus wept.
@sonny<...>
I'd suggest you to ask your late dog about how smart you are, you still may get some clever hints from it. Not sure about your kids - if they have gone after their father, then ... guess you already understood what they are in for. Live and learn (if you can)..
You should stick to comedy. You clear have a sense of humor.
Let me just say about your code, since you don't seem to see the issue, that if the LCA node is one million levels down the tree, you are going to find the two nodes one million times. Why not find them just one time?
Btw, the solution is not constant space. Every recursive call allocates multiple pointers. So it's O(n) space.
Node* LCP(Node* tree, Node* node1, Node* node2, int* found = null)
{
if (tree == null) return null;
if (found == null) found = &0;
Node* result;
int rightFound = 0;
int leftFound = 0;
if (tree->rightchild) result = LCP(tree->rightchild, node1, node2, &rightFound);
*found = 2;
if (rightFound == 2) return result;
if (tree->leftchild) result = LCP(tree->rightchild, node1, node2, &leftFound);
if (leftFound == 2) return result;
*found = leftfound + rightfound;
if (*found == 2) return tree;
return null;
}
Guys how do you Turn the following class into a Singleton:
public class Earth {
public static void spin() {}
public static void warmUp() {}
}
public class EarthTest {
public static void main(String[] args) {
Earth.spin();
Earth.warmUp();
}
}
My friend came up with this brilliant answer. He said :
1. List the pre and post order traversal of the tree.
(Now observe that the common parent of the two nodes will occur before both the nodes and after both the nodes in the pre and post order traversal listing respectively.)
2. In a pre-order traversal list place all the nodes occurring before n1 and n2 in a hash map h1
Preorder traversal P1: [....] n1....n2......
3. Now traverse the nodes which occur after both the Nodes n1 and n2. -
Postorder Traversal P2: ....n2....n1[....]
4. Return the first node which maps to the hash map h1 in the list P2
Slightly different version to sonny.c.patterson!!
- praveen November 08, 2012Please comment, if anything is wrong.