## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 3 vote

Quick (without thought!) recursive version

``````void Delete(Tree *root) {
if (root == NULL) return;
for (int i = 1; i <= root->numChildren; i++) {
Delete(root->Child(i));
}
free(root);
}``````

Comment hidden because of low score. Click to expand.
0

Quick Thought Answer sometimes works extremely well!

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

the video is

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

{
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;

delete_nodes_iterative(root);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Given the condition of the tree being not a binary tree, we cannot assume to be BT or BST and apply postorder.
I think the solution would be DFS traversal with deleting the leaf node.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.