sonny.c.patterson
BAN USERYes, the negative sign is just a bit. You would have to change to an unsigned integer to index the array.
- sonny.c.patterson December 25, 2012In any case the question only applies to the contains function, the LCA function certainly is not.
- sonny.c.patterson November 23, 2012Is this tail recursive? I don't think so because of the double call.
- sonny.c.patterson November 23, 2012Btw, the solution is not constant space. Every recursive call allocates multiple pointers. So it's O(n) space.
- sonny.c.patterson November 23, 2012It's not a BST
- sonny.c.patterson November 23, 2012You 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?
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.c.patterson November 22, 2012Give it a private constructor and instantiate an object to a static member reference?
- sonny.c.patterson November 21, 2012Give it a private constructor and instantiate an object to a static member reference?
- sonny.c.patterson November 21, 2012The best solution that is O(1) is the array of max int bits. If int is 32 bit that's 512MiB.
- sonny.c.patterson November 11, 2012For a 64 bit integer that's enormous, on the order of exabytes I think. In other words though it is technically O(1) that constant and is many orders of magnitude larger than O(n) or even O(n^2).
- sonny.c.patterson November 08, 2012It 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.
- sonny.c.patterson November 08, 2012Very 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.
- sonny.c.patterson November 08, 2012Ugh
- sonny.c.patterson November 08, 2012It's the lca of two nodes, not the lca of two values. If you wanted to find the lca of nodes with values that duplicate ancestor nodes this would give incorrect results. You need to compare addresses, no values.
- sonny.c.patterson November 08, 2012Node* 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;
}
- sonny.c.patterson November 08, 2012
It's covered.
- sonny.c.patterson December 25, 2012