Amazon Interview Question Software Engineer / Developers
1. Convert BST to single Pointer LL. --- O(N)
2. Start delete node from LL one after another. --- O(N)
Total Complexity: O(2N)
Is the above solution Aceptable ?
Node temp=root,trash;
while(root){
while(root.right!=null)
temp=root.right;
if(root==temp){
trash=root;
root=root.left;
temp=root;
free(trash);
continue;
}
temp.right=root.left;
trash=root;
root=root.right;
free(trash)
}
Correct me if i am wrong, but in languages like java, an object that is not referred to by any other object is deleted, so root.finalize() should be enough rest all will be taken care by the java garbage collector. Any views?
I think that deleting the nodes as they are encountered in a breadth first search(BFS) would work. Depth first search cannot be used because then we cannot delete nodes as we encounter them but for BFS this is possible. The time complexity would be O(n) since each node is visited exactly once and deleted.
Will below solution work.
First delete Left subtree then right subtree. Then free the Node.
I guess complexity will be O(n) only.
delect (Node root)
{
if(root->left !=null)
delete(root->left);
if(root->right != null)
delete(root->right);
free(root)
}
I am also thinking same because if we delete root first then we loss the access to others..but if we do postorder then we can delete tree easily.It will use system stack and recursion.
if you want to do postorder without recursion then we can do it by using stack and flag.
Maintain 2 stacks one for the parent and other for the sibling.... keep throwing the root and the sibling in the stacks(maintain some info if the sibling is present or not) if the node is not left with any children remove it and move ot its sibling in the other stack.
Do this in a while loop and the siblings will move into the main root stack.
it can be done in O(n) and O(1) space by manipulating the left/right child pointers.
Below is pseudo code:
*** I haven't compiled this.
- Anonymous February 17, 2011void DeleteTree (node* root) { node* tempRoot = root; node* tempLeft = root->left; node* tempRight = root->right; node* tempNode = NULL; while (tempLeft || tempRight) { if (tempLeft) { tempNode = tempLeft->left; tempLeft->left = tempRoot; tempRoot = tempLeft; tempLeft = tempNode; continue; /*this is important*/ } tempRight = tempRoot->right; if (tempLeft == NULL && tempRight == NULL) { tempNode = tempRoot->left; delete (tempRoot); tempRoot = NULL; tempRoot = tempNode; tempLeft = tempRoot->right; } else { tempNode = tempRight->left; tempRight->left = tempRoot; tempLeft = tempNode; tempRoot = tempRight; } } delete (tempRoot); }