## 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
of 0 votes

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
of 0 votes

the video is
youtube.com/watch?v=qZbmY-2Y26Y

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

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

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.

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More