Insert and delete in binary tree
Reference
import java.util.ArrayDeque;
class BinaryTree {
private static Node root;
static Node insertRecursive(Node current, Node previous, int data) {
if(current == null) {
Node node = new Node(data);
if(previous == null) {
// it's first node in tree
return node;
} else if(data < previous.data) {
// insert into left child
previous.left = node;
} else {
previous.right = node;
}
return previous;
}
if(data < current.data) {
return insertRecursive(current.left, current, data);
}
return insertRecursive(current.right, current, data);
}
static Node insertRecursive2(Node current, int data) {
if(current == null) {
return new Node(data);
}
if(data < current.data) {
current.left = insertRecursive2(current.left, data);
} else if(data > current.data) {
current.right = insertRecursive2(current.right, data);
}
return current;
}
static Node insert(Node node, int data) {
Node newNode = new Node(data);
// if tree is empty
if(node == null) {
return newNode;
}
Node previous, current;
current = previous = node;
// iterate thorugh tree until don't find element or reach to end
while(current != null) {
if(current.data == data) {
// data exists in the tree
return node;
}
previous = current;
current = data < current.data ? current.left : current.right;
}
if(data < previous.data) {
previous.left = newNode;
} else {
previous.right = newNode;
}
return node;
}
// TODO
static Node delete(Node node, int data) {
/* Case 1: Base Case: If the tree is empty */
if(node == null) {
return null;
}
/* Otherwise, recur down the tree */
if(data < node.data) {
node.left = delete(node.left, data);
return node;
} else if(data > node.data) {
node.right = delete(node.right, data);
return node;
}
// Case 2: node with only one child or no child
else if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
}else {
int nodeData = node.data;
// Case 3:
// we found the key, delete it. We can use inorder predecessor or inorder
// successor to replace this node to reference it's sub trees
// we are deciding based on height of left or right sub tree for chosing inorder
// predecessor or successor
Node inorderPredOrSucc = null;
if(height(node.left) > height(node.right)) {
inorderPredOrSucc = inorderPredecessor(node.left);
node.data = inorderPredOrSucc.data;
node.left = delete(node.left, inorderPredOrSucc.data);
} else {
inorderPredOrSucc = inorderSuccessor(node.right);
node.data = inorderPredOrSucc.data;
node.right = delete(node.right, inorderPredOrSucc.data);
}
}
return node;
}
static int height(Node node) {
if(node == null) {
return 0;
}
int lHeight = height(node.left);
int rHeight = height(node.right);
return (lHeight > rHeight ? lHeight : rHeight) + 1;
}
static Node inorderPredecessor(Node node) {
while(node != null && node.right != null) {
node = node.right;
}
return node;
}
static Node inorderSuccessor(Node node) {
while(node != null && node.left != null) {
node = node.left;
}
return node;
}
static void preOrderTraversal(Node node) {
if(node == null) {
return;
}
System.out.print(node.data + " ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
public static void main (String[] args) {
// insert operations
int[] data = new int[] {9, 150, 5, 200, 16, 80, 12, 30, 6,
90, 15, 50, 20, 160, 8, 120, 3, 60};
// root = insertRecursive2(root, null, data[0]);
root = insertRecursive2(null, data[0]);
for(int i = 1; i < data.length; i++) {
// insertRecursive2(root, null, data[i]);
insertRecursive2(root, data[i]);
}
System.out.println("In order traversal :");
preOrderTraversal(root);
// delete operations
for(int i = 0; i < 10; i++) {
delete(root, data[i]);
}
System.out.println("\nPre order traversal after deleting 10 nodes : ");
preOrderTraversal(root);
}
private static class Node {
Node left;
int data;
Node right;
public Node(int data) {
this.data = data;
}
}
}
Output
In order traversal :
9 5 3 6 8 150 16 12 15 80 30 20 50 60 90 120 200 160
Pre order traversal after deleting 10 nodes :
15 8 3 120 20 60 50 160
Comments
Post a Comment