## Google Interview Question

SDE1s**Country:**United States

Traverse the tree in pre order, so any node is erased before it's children. Here is the high level algorithm.

```
isRootErased := false
forest := []
eraseNodes(node, parent):
if node is null
return
if shouldBeErased(node):
if parent is null:
isRootErased := true
else if parent.left is node:
parent.left := null
else:
parent.right := null
if node.left is not null:
forest.push(node.left)
if node.right is not null:
forest.push(node.right)
eraseNodes(node.left, node)
eraseNodes(node.right, node)
eraseNodes(root, null)
if not isRootErased:
forest.push(root)
return forest
```

Processing each node take O(1), so time complexity is O(N), where N is the number of nodes.

Regarding the follow up, it depends. Suppose you are given a list of K nodes to erase. Finding each of them would take O(log N) if the tree is balanced. So overall complexity in time would be O(K log N), which is better than O(N) if K is small. In the worst case, K = N and we get O(N log N), which is worse.

```
class node
{
public:
int val;
node* left;
node* right;
node( int v): val(v), left( nullptr), right(nullptr)
{}
};
node* eraseNodes(node* root, vector<node*>& result, function< bool(node*) >& shouldBeErased )
{
if(!root) return nullptr;
// check if leaf node
if( !root->left && !root->right )
{
if( shouldBeErased(root) )
{
delete root;
return nullptr;
}
else
{
return root;
}
}
root->left = eraseNodes( root->left, result, shouldBeErased );;
root->right = eraseNodes(root->right, result, shouldBeErased);;
if( shouldBeErased(root) )
{
if( root->left ) result.push_back(root->left);
if( root->right ) result.push_back( root->right);
return nullptr;
}
return root;
}
```

```
void Erase(Node *n, vector<Node *> &forest, Node *parent = NULL)
{
if (n) {
Erase(n->left_, forest, n);
Erase(n->right_, forest, n);
if (ShouldBeErased(n)) {
if (parent) {
if (parent->left_ == n) {
parent->left_ = NULL;
} else {
parent->right_ = NULL;
}
}
} else if (parent == NULL ||
ShouldBeErased(parent))
{
forest.push_back(n);
}
}
}
```

Solution for the first part.

Follow-up: Yes, it will be simpler to solve, since searching for the node in the forest will be faster. In the case of the BST, only the find_node function needs to be changed in the below implementation, everything else remains the same.

Output:

- havanagrawal November 13, 2017