Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
You can understand the solution for a binary tree and then you can proceed for any n-ary tree basically the thing is all the child subtrees should be deleted before the node itself. So it follows kind of postorder traversal. You can watch a very helpful link to understand this concept at youtube.com/watch?v=qZbmY-2Y26Y
I would just say how is the tree implemented?
1. Using child-sibling concept?
2. Using only child concept & no sibling?
my_delete(root) //case 1
{
if(root)
{
my_delete(root->child);
my_delete(root->sibling);
free(root);
}
}
Assume N -ary tree.
my_delete(root) //case 2
{
if(root)
{
for(i=0;i<N;i++)
my_delete(root->child[i]);
free(root);
}
}
Below is the iterative implementation using a single stack of size of the tree height. Also including the driver program to test it (complete working version).
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
struct Node {
int data;
vector<Node*> children;
};
Node *add_node(Node *root, int data)
{
if (NULL == root)
return NULL;
Node *node = new Node;
node->data = data;
root->children.push_back(node);
return node;
}
void delete_nodes_iterative(Node *root)
{
stack<Node*> stnodes;
Node *cur = root;
stnodes.push(cur);
while (true) {
cur = stnodes.top();
printf("size: %d; cur: %d\n", stnodes.size(), cur->data);
if(cur->children.size() > 0) {
stnodes.push(cur->children[0]);
cur->children.erase(cur->children.begin()); // unlink from parent but do not delete the node itself
}
else { // leaf node
stnodes.pop();
printf("\tdel: %d\n", cur->data);
delete cur;
}
if (stnodes.empty())
break;
}
}
int main()
{
Node *root = new Node;
root->data = 1;
Node *n2 = add_node(root, 2);
Node *n3 = add_node(root, 3);
Node *n4 = add_node(root, 4);
Node *n5 = add_node(n2, 5);
Node *n6 = add_node(n2, 6);
Node *n7 = add_node(n2, 7);
Node *n8 = add_node(n3, 8);
Node *n9 = add_node(n3, 9);
Node *n10 = add_node(n3, 10);
Node *n11 = add_node(n4, 11);
Node *n12 = add_node(n4, 12);
Node *n13 = add_node(n4, 13);
Node *n14 = add_node(n4, 14);
Node *n15 = add_node(n5, 15);
Node *n16 = add_node(n5, 16);
Node *n17 = add_node(n5, 17);
Node *n18 = add_node(n6, 18);
Node *n19 = add_node(n11, 19);
Node *n20 = add_node(n11, 20);
Node *n21 = add_node(n16, 21);
Node *n22 = add_node(n16, 22);
delete_nodes_iterative(root);
}
Quick (without thought!) recursive version
- Anonymous July 25, 2012