CareerCup

node *find(node *root, int val) {
if (!root) return NULL;

if (root->val == val) return root;

if (val < root->val) return find(root->left);
else return find(root->right);
}

He is asking for finding the element and deleting it as well. Not just finding the element.

@nunbit Is the question for a binary tree or binary search tree?

Node find(int num Node root)
{
if(rooyt == null)
return null

if(root.value== num)
return node

else
{
if(root.leftChild != null)
return find(root.leftChild)

if(root.rightChild != null)
return find(root.rightChild)

}


}

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