Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Here is the code using bfs:
void Delete (Tree *root) {
if (!root) return;
Queue <Tree *> q;
q.enQ(root);
while(!q.isEmpty()) {
Tree * cur = q.deQ();
if (cur->left) q.enQ(cur->left);
if (cur->right) q.deQ(cur->right);
delete cur;
}
}
Well, here you are pushing nodes into the queue, and popping them off the queue. How does that delete the tree? It remains just as it is.
If the question is to be coded in java, can we say that we can remove the reference to the tree and garbage collector will take care of it?
@yinyan - In java, the memory management is automatic (i.e. JVM is responsible for it and not the application developers). So you're idea of removing only the reference of the root of the tree would eventually free all the memory. However, for the sake of understanding this question, the java-equivalent would be: How could you remove all the parent child references in a binary-tree without recursive algorithm!
void DeleteTree(Node* root)
{
std::stack<Node*> nodes;
nodes.push( root);
while( ! nodes.empty())
{
Node* topNode = nodes.top();
nodes.pop();
if ( topNode->left )
nodes.push(topNode->left);
if ( topNode->right )
nodes.push(topNode->right);
delete topNode;
}
}
One thing to be aware of here, is that using a stack makes this a depth first search. Traditionally a BFS traversal uses a Queue. In an interview you might get dinged for not understanding the nuance, though this solution will work fine (level order depth first search) however it is not the classic approach.
you don't have to use any storage actually. It's a postorder traversal that eliminates the leaves.
void delete_tree_nonrecursive(Node** root)
{
if (!root || !(*root) ) return;
Node *node = *root; // start from the root
while(1)
{
if (node->left)
node = node->left; //explore left
else if (node->right)
node = node->right; // explore right
else if (node->parent) // back up
{
Node *leaf = node; // save pointer to leaf
node = node->parent; // move up to parent
if (node->left == leaf)
node->left = 0; // disconnect leaf
else
node->right = 0; // disconnect leaf
delete leaf; // delete leaf
}
else
{
delete node; // delete root
*root = 0; // change the pointer to root node to NULL
break; //stop
}
}
}
here, storing parent node takes O(n) additional space.
Similar to usage of stack for BFS. -- O(N)
@mrb: there's no storage of parents here, in fact you don't store anytthing [except for a local swap operation].
The algorithm just navigates in the tree, exploring towards children, deleting leaves and backing up when a leaf has been deleted.
If i am understanding the node structure for the tree node is as
struct node
{
struct node* left;
struct node* right;
struct node* parent;
int data;
};
So basically we are using extra space already for each node.
Correct me if i am wrong?
check this O(1) implementation ...
{
struct node * getleftmost(struct node * somenode)
{
while(somenode->left)
somenode=somenode->left;
return somenode
}
void delete(struct node *root)
{
if(root==NULL)
return ;
while(root)
{
temp=root;
if(root->left){
if(root->right)
getleftmost(root)->left=root->right;
else
root=root->left;
}
else if (root->right)
root=root->right;
else
root=NULL;
free(temp);
}
}
This is a brilliant solution if you're trying to avoid using parent or a stack. However, it's not O(1). In fact it's pretty damn expensive since you're calling getleftmost() so often. Haven't tried to compute how much exactly but it's gotta be expensive with all the right subtrees being slapped on to the left most leaf.
i do agree...its costly ...i actually meant o(1) space implementation ..
there is no point if u try to use a stack or queue ...
because recursion anyway takes O(n) space on the stack
just check this function ...which converts the tree to list
{
struct node * converttolist(struct node *root)
{
if(root ==NULL)
return NULL;
struct node *realhead=root;
struct node *head=root;
while(head->left)
head=head->left;
while(root)
{
if(root->right){
root=root->right;
while(root){
head->left=root;
head=head->left;
root=root->left);
}
}
root=root->left;
}
return realhead;
}
}
now that i got a list i can just traverse the list to delete tree
void delete(Node root){
Stack<Node> S = new Stack<Node>();
Node current = root;
while (current.leftChild != null){
S.push(current);
current = current.leftChild;
current.Visited = false;
}
while (!S.isEmpty()){
current = S.pop();
if (!current.Visited){
S.push(current);
current.Visited = true;
current = current.right;
while (current.leftChild != null){
S.push(current);
current.Visited = false;
current = current.leftChild;
}
}else{
delete(current);
}
}
return;
}
void DeleteTree(Node root){
deleteTree(root);
root = null;
}
void deleteTree(){
if(root == null) return;
Queue<Node> q = new LinkedList<Node>();
//do level order traversal
q.add(root);
while(!q.isEmpty()){
Node node = q.poll();
if(node.left != null){
q.add(node.left);
}//if
if(node.right != null){
q.add(node.right);
}//if
}//while
}
This could be done with a level order traversal (or bfs tree traversal). if the interviewer didn't want that you could simulate a threaded bst using what is called Morris Traversal.
- Bob September 19, 2012