Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
deleting a node directly would result in dangling pointers, so first check if any of the child node is leaf or not and if leaf then remove the child reference and free memory.
void prune(Node *root) {
if(root == NULL) return;
if(root->left != NULL) {
Node *leftChild = root->left;
if(leftChild->left == NULL && leftChild->right == NULL) {
root->left = NULL;
free(leftChild);
}
}
if(root->right != NULL) {
Node *rightChild = root->right;
if(rightChild->left == NULL && rightChild->right == NULL) {
root->left = NULL;
free(rightChild);
}
}
prune(root->left);
prune(root->right);
}
You need to define pruning, as it can mean a lot of things. In the most general sense, you can be pruning either the breadth or the height of the tree.
The most common is to prune all the leaf nodes. Something like this might work:
- AK February 27, 2014