Google Interview Question
Java DevelopersCountry: United States
I assume connected is adjacent and the Node has no parent pointer.
Node* find_local_min(Node *root)
{
stack<pair<Node*, Node*>> s;
s.push({ root, root });
while (!s.empty()) {
Node* p = s.top().first; // parent of current, none = root if p = n
Node* c = s.top().second; // current
int cv = c->value_; // current value
s.pop();
if (c->left_ != nullptr && c->right_ != nullptr
&& cv < p->value_ && cv < c->left_->value_ && cv < c->right_->value_) {
return c;
}
if (c->left_ != nullptr) s.push({ false, c->left_ });
if (c->right_ != nullptr) s.push({ false, c->right_ });
}
return nullptr;
}
I assume the node is a local minimum node, if the node's value is less than the node's parent's value, and less than the node's children's values.
void LocalMinNodes(Node *n, vector<Node *> &out, Node *parent = NULL)
{
if (n) {
if ((!parent || n->val_ < parent->val_) &&
(!n->left_ || n->val_ < n->left_->val_) &&
(!n->right_ || n->val_ < n->right_->val_))
{
out.push_back(n);
}
LocalMinNodes(n->left_, out, n);
LocalMinNodes(n->right_, out, n);
}
}
Can you give an example? What do you mean by connected here? Are we talking about direct or transitive connectivity? If it's direct, a node i a binary tree is connected to just two child nodes (at most). But if we are talking about transitive connectivity, a node is connected to all the nodes in its left and right subtrees.
- Anonymous December 01, 2017