Pergunta de entrevista da empresa Meta
Write a function to determine if a bin tree is a valid BST. I wrote a fully working solution in 3-5 minutes. It was also the most optimal but maybe because she needed to kill time, she asked me to rewrite it in what she thought was optimal (her reasoning didn't make much sense). Then she asked me for time and space requirements of the solutions. I said O(n) for both which is correct but she insisted that the space requirement was O(logn) which is wrong.
Respostas da entrevista
I don't think she is wrong. You can validate a BST in O(n) time with O(logn) space. Just do an inorder walk on the tree and compare with previous node, if you are always increasing then it is a valid BST.
I think your above solution is incorrect. All you're doing is checking if the value on the left is smaller and the value on the right is larger. But this is wrong. You need to also keep track of the minimum and maximum range for the subtrees. Because by your logic, a tree with say, 5 as the root and 13 as a right child and 3 as a left child of 13 would be valid although that is not true since 3 has to be on the left side of 5.
Also wikipedia says that the worst case space requirement for a BST is O(n) http://en.wikipedia.org/wiki/Binary_search_tree
We only use O(log n) additional space if the BST is balanced, which was not mentioned in the question. Otherwise, the worst case is O(n) additional memory.
I think she was right. The worst case space requirement for implementing a BST is O(n), however checking if a tree is a BST requires only O(log (N)) additional space. My solution would compute recursively the (min,max) for each subtree and check if maximum element from the left subtree is smaller than the root's element and the minimum element of the right subtree is bigger than the root's element. The log(N) additional space is used because of the stack to implement it recursively. Not sure if this is optimal in space though.
sorry pal, but she was right
Even if the tree is not balanced: space=O(logn) time =O(n)
Actually, only if the tree is balanced the we will get to O(n)
If it is a list of single childs then O(1)
bool isValidBst(Node* n)
{
deque nodes;
nodes.push_back(n);
while(!nodes.empty())
{
if (!isValid(nodes.front())) return false;
nodes.pop_front();
if (n->left) nodes.push_back(n->left);
if (n->right) nodes.push_back(n->right);
}
return true;
}
bool isValid(Node* n)
{
if (n == NULL) return true;
if (n->left && n->left->val > n->val) return false;
if (n->right && n->right->val val) return false;
return true;
}