CareerCup

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.

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);
	}
}