CareerCup

Q1.

Node getCommonAncestor(Node root, Node n1, Node n2) {
	if (root == null) {
		return null;
	}

	int largerValue = n1.value > n2.value ? n1.value : n2.value;
	int smallerValue = n1.value > n2.value ? n1.value : n2.value;

	if (root.value >= smallerValue && root.value <= largerValue) {
		return root;
	}

	if (root.value > largerValue) {
		return getCommonAncestor(root.left, n1, n2);
	}

	if (root.value < smallerValue) {
		return getCommonAncestor(root.right, n1, n2);
	}
}

Q2.

Node getCommonAncestor(Node root, Node n1, Node n2) {
	if (root == null) {
		return null;
	}

	int largerValue = n1.value > n2.value ? n1.value : n2.value;
	int smallerValue = n1.value > n2.value ? n1.value : n2.value;

	if (root.value >= smallerValue && root.value <= largerValue) {
		if (root.left.value == root.value) {
			return getCommonAncestor(root.left, n1, n2);
		} else {
			return root;
		}
	}

	if (root.value > largerValue) {
		return getCommonAncestor(root.left, n1, n2);
	}

	if (root.value < smallerValue) {
		return getCommonAncestor(root.right, n1, n2);
	}

}

Q1.

Node getCommonAncestor(Node root, Node n1, Node n2) {
	if (root == null) {
		return null;
	}

	int largerValue = n1.value > n2.value ? n1.value : n2.value;
	int smallerValue = n1.value > n2.value ? n1.value : n2.value;

	if (root.value >= smallerValue && root.value <= largerValue) {
		return root;
	}

	if (root.value > largerValue) {
		return getCommonAncestor(root.left, n1, n2);
	}

	if (root.value < smallerValue) {
		return getCommonAncestor(root.right, n1, n2);
	}

}

Q3.

Node getCommonAncestor(Node root, Node n1, Node n2) {
	bool fakeBool = false;
	return getCommonAncestor(root, n1, n2, &fakebool, &fakebool);
}

Node getCommonAncestor(Node root, Node n1, Node n2, bool& isN1Found, bool& isN2Found) {
	if (root == null) {
		return null;
	}

	bool _isN1Found = false;
	bool _isN2Found = false;
	if (root == n1) {
		_isN1Found = true;
		isN1Found = true;
	}

	if (root == n2) {
		_isN1Found = true;
		isN2Found = true;
	}

	Node possibleResult = getCommonAncestor(root.left, n1, _isN1Found, _isN2Found);
	if (possibleResult != null) {
		return possibleResult;
	}

	if (_isN1Found) {
		isN1Found = true; 
	}

	if (_isN2Found) {
		_isN2Found = true;
	}

	if (_isN1Found && _isN2Found) {
		return root;
	}

	Node possibleResult = getCommonAncestor(root.right, n1, _isN1Found, _isN2Found);
	if (possibleResult != null) {
		return possibleResult;
	}

	if (_isN1Found) {
		isN1Found = true; 
	}

	if (_isN2Found) {
		_isN2Found = true;
	}

	if (_isN1Found && _isN2Found) {
		return root;
	}

	return null;
}

Node const *LowestAncestorQ1(Node const *n, int val1, int val2)
{
    while (n) {
        if (val1 > n->val_ &&
            val2 > n->val_)
        {
            n = n->right_;
        } else if (
            val1 < n->val_ &&
            val2 < n->val_)
        {
            n = n->left_;
        } else {
            break;
        }
    }
    return n;
}

Node const *LowestAncestorQ2(Node const *n, int val1, int val2)
{
    while (n) {
        if (val1 > n->val_ &&
            val2 > n->val_)
        {
            n = n->right_;
        } else if (
            val1 < n->val_ &&
            val2 < n->val_)
        {
            n = n->left_;
        } else {
            if (n->left_ &&
                n->left_->val_ == n->val_)
            {
                n = n->left_;
            } else {
                break;
            }
        }
    }
    return n;
}

int LowestAncestorQ3(Node const *n, int val1, int val2, Node const **ancestor)
{
    int count = 0;
    if (!*ancestor &&
        n)
    {
        if (n->val_ == val1 ||
            n->val_ == val2)
        {
            ++count;
        }
        count += LowestAncestorQ3(n->left_, val1, val2, ancestor);
        count += LowestAncestorQ3(n->right_, val1, val2, ancestor);
        if (count >= 2 &&
            !*ancestor)
        {
            *ancestor = n;
        }
    }
    return count;
}