Building Binary Search Tree in Java - Insertion

In computer science, a binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties: [from wiki]

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Node Structure.
Each node has left-child, right-child, height, value, and parent member. In fact, the parent member is not necessary, but it is added for easy understanding of binary tree, and especially when deleting node from the tree. With children of node, the parent of a node can be found easily. (see BinarySearchTree.java)

The setHeight() and getHeight() methods are not necessay too for binary search tree. They need for balanced tree such as AVL tree and Red-Black Tree.

download Node.java

public class Node {
private Node leftChild;
private Node rightChild;
private Node parent;
private int value;
private int height;

public Node(Node p, Node l, Node r, int v, int h) {
leftChild = l;
rightChild = r;
value = v;
height = h;
parent = p;
}

public Node(int v, Node p) {
this(p, null, null, v, 0);

}
public Node (int v) {
this(null, null, null, v, 0);
}

public boolean isBalanced() {
if(leftChild == null && rightChild == null)
return true;
else if (leftChild == null)
return rightChild.getHeight() == 0;
else if (rightChild == null)
return leftChild.getHeight() == 0;

return Math.abs(leftChild.getHeight()- rightChild.getHeight()) < 2;
}

public void setParent(Node parent) {
this.parent = parent;
}

public Node getParent() {
return parent;
}

public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}

public Node getLeftChild() {
return leftChild;
}

public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}

public Node getRightChild() {
return rightChild;
}

public void setValue(int value) {
this.value = value;
}

public int getValue() {
return value;
}

public void setHeight() {
if(leftChild == null && rightChild == null)
height = 0;
else if (leftChild == null)
height = rightChild.getHeight() + 1;
else if (rightChild == null)
height = leftChild.getHeight() + 1;
else
height= leftChild.getHeight() >= rightChild.getHeight()?
leftChild.getHeight() + 1: rightChild.getHeight() +1;
}

public int getHeight() {
setHeight();
return height;
}
}

Building BST, inserting node.
Insertion begins as a search would begin; if the root is not equal to the value, we search the left or right subtrees as before. Eventually, we will reach an external node and add the value as its right or left child, depending on the node's value. In other words, we examine the root and recursively insert the new node to the left subtree if the new value is less than the root, or the right subtree if the new value is greater than or equal to the root.

download BinarySearchTree.java

public class BinarySearchTree {
private Node root;

public BinarySearchTree(Node root) {
this.root = root;
}
public BinarySearchTree() {
this.root = (Node)null;
}

private void setRoot(Node r) {
root = r;
}

private Node getRoot() {
return root;
}

public Node findParent(int value, Node node) {
if (node.getValue() == value)
return (Node)null; // root itself
else if(node.getLeftChild() != null && node.getLeftChild().getValue() == value)
return node;
else if(node.getRightChild() != null && node.getRightChild().getValue() == value)
return node;
else if (node.getValue() > value)
return findParent(value, node.getLeftChild());
else
return findParent(value, node.getRightChild());
}

public Node insertNode(int value) {
return insertNode(value, null, null);
}

public Node insertNode(int value, Node node, Node parent) {
if(node == (Node)null)
node = new Node(parent, null, null, value, 0);
else if (value < node.getValue())
node.setLeftChild(insertNode(value,node.getLeftChild(), node));
else if (value > node.getValue())
node.setRightChild(insertNode(value, node.getRightChild(), node));
node.setHeight();
return node;
}

/* in-order traversal for showing inside of tree */
public void traverseInOrder(Node node) {
if(node.getLeftChild() != (Node)null)
traverseInOrder(node.getLeftChild());
System.out.print("Value: [" + node.getValue() + "], Height: [" +
node.getHeight() + "], Parent: [");

Node n = findParent(node.getValue(), getRoot());
if(n == (Node)null)
System.out.println("root]");
else
System.out.println(n.getValue() + "]");

if(node.getRightChild()!= (Node)null)
traverseInOrder(node.getRightChild());
}

public static void main(String[] args) {
TestCode tree = new TestCode();
Node root = new Node(5);
tree.setRoot(root);
int[] input = {7, 9, 3, 1, 2, 8, 10, 6};

for (int i = 0; i<input.length; i++)
tree.setRoot(tree.insertNode(input[i], root, null));

tree.traverseInOrder(tree.getRoot());
}
}

Posted in Algorithm, Binary Search, Binary Search Tree, C, Insert Binary Tree, Java, Programming, Search Algorithm, Tree, Tree Structure