Ebay Interview Question
Software Engineer / DevelopersVoid delete(key value, Node root){
Node toBeDeleted = find(value,root);
if(toBeDeleted.rightChild == Null && toBeDeleted.leftChild == Null){
if(toBeDeleted.parent.RightChild.value == toBeDeleted.value) toBeDeleted.parent.RightChild = Null;
if(toBeDeleted.parent.LeftChild.value == toBeDeleted.value) toBeDeleted.parent.LeftChild = Null;
}
else if(toBeDeleted.rightChild == Null && toBeDeleted.leftChild != Null){
toBeDeleted.leftChild.parent = toBeDeleted.parent;
if(toBeDeleted.parent.RightChild.value == toBeDeleted.value) toBeDeleted.parent.RightChild = Null;
if(toBeDeleted.parent.LeftChild.value == toBeDeleted.value) toBeDeleted.parent.LeftChild = Null;
}
else if(toBeDeleted.rightChild != Null && toBeDeleted.leftChild == Null){
toBeDeleted.RightChild.parent = toBeDeleted.parent;
if(toBeDeleted.parent.RightChild.value == toBeDeleted.value) toBeDeleted.parent.RightChild = Null;
if(toBeDeleted.parent.LeftChild.value == toBeDeleted.value) toBeDeleted.parent.LeftChild = Null;
}
else{
Node newNode = find_Successor(toBedDeleted);
delete(newNode);
toBeDeletedNode.value = newNode.value;
}
}
use the find method given above by anshulzuke
public class BinaryTree {
Node root;
public void addNode(int key, String name) {
Node newNode = new Node(key, name);
if (root == null) {
root = newNode;
} else {
Node focusNode = root;
Node parent;
while (true) {
parent = focusNode;
if (key < focusNode.key) {
focusNode = focusNode.leftChild;
if (focusNode == null) {
parent.leftChild = newNode;
return;
}
} else {
focusNode = focusNode.rightChild;
if (focusNode == null) {
parent.rightChild = newNode;
return;
}
}
}
}
}
public boolean remove(int key) {
Node focusNode = root;
Node parent = root;
boolean isItALeftChild = true;
while (focusNode.key != key) {
parent = focusNode;
if (key < focusNode.key) {
isItALeftChild = true;
focusNode = focusNode.leftChild;
} else {
isItALeftChild = false;
focusNode = focusNode.rightChild;
}
if (focusNode == null) {
return false;
}
}
if (focusNode.leftChild == null && focusNode.rightChild == null) {
if (focusNode == root) {
root = null;
} else if (isItALeftChild) {
parent.leftChild = null;
} else {
parent.rightChild = null;
}
} else if (focusNode.rightChild == null) {
if (focusNode == root) {
root = focusNode.leftChild;
} else if (isItALeftChild) {
parent.leftChild = focusNode.leftChild;
} else {
parent.rightChild = focusNode.leftChild;
}
} else if (focusNode.leftChild == null) {
if (focusNode == root) {
root = focusNode.rightChild;
} else if (isItALeftChild) {
parent.leftChild = focusNode.rightChild;
} else {
parent.rightChild = focusNode.leftChild;
}
} else {
Node replacement = getReplacementNode(focusNode);
if (focusNode == root) {
root = replacement;
} else if (isItALeftChild) {
parent.leftChild = replacement;
} else {
parent.rightChild = replacement;
}
replacement.leftChild = focusNode.leftChild;
}
return true;
}
public Node getReplacementNode(Node replacedNode) {
Node replacementParent = replacedNode;
Node replacement = replacedNode;
Node focusNode = replacedNode.rightChild;
while (focusNode != null) {
replacementParent = replacement;
replacement = focusNode;
focusNode = focusNode.leftChild;
}
if (replacement != replacedNode.rightChild) {
replacementParent.leftChild = replacement.rightChild;
replacement.rightChild = replacedNode.rightChild;
}
return replacement;
}
public static void main(String[] args) {
BinaryTree theTree = new BinaryTree();
theTree.addNode(50, "Boss");
theTree.addNode(25, "Vice President");
theTree.addNode(15, "Office Manager");
theTree.addNode(30, "Secretary");
theTree.addNode(75, "Sales Manager");
theTree.addNode(85, "Salesman 1");
System.out.println("\nRemove key 25");
theTree.remove(25);
}
}
class Node {
int key;
String name;
Node leftChild;
Node rightChild;
Node(int key, String name) {
this.key = key;
this.name = name;
}
public String toString() {
return name + " has the key " + key;
}
}
node *find(node *root, int val) {
- nunbit romance June 05, 2007if (!root) return NULL;
if (root->val == val) return root;
if (val < root->val) return find(root->left);
else return find(root->right);
}