## Monday, 26 August 2013

### Data Structure : Binary Search Tree

This blog describes the Internal Working of TreeMap. This is a Binary Search Tree. Similar to java.util.TreeMap.
Binary Search Tree (BST) is a Data Structure which places the data in sorted order. Each Node has 2 pointers/references left and right. If the data to be inserted is smaller than the current node than the new node is attached at the left of the current node. If the data to be inserted is greater than the current node than the new node is attached at the right of the current node.

In case the data is less than current node and if the current node already has a node attached to the left than the left-attached-node data is checked. This is recursive till the left node is null. Same is done for right node if the data to be attached is greater than current node. Below is the program with detail comments.

```package com.tree;

class Node {
public int data;
public Node left;
public Node right;

}

public class BST {

static Node start;

public static void main(String[] args) {

display(start);

}

private static void add(int i) {
// Create new node
Node p = new Node();
p.data = i;
if (start == null) {
start = p;
} else {
placeNode(p, start);
}
}

private static void placeNode(Node p, Node target) {

//Check if p.data is less than target.data
//If yes than check if target.left is null
//If yes than attach new node to target.left
//If no than call placeNode with target as target.left
if (p.data < target.data) {
if (target.left == null) {
target.left = p;
} else {
placeNode(p, target.left);
}
}
//If yes than check if target.right is null
//If yes than attach new node to target.right
//If no than call placeNode with target as target.right
if (p.data > target.data) {
if (target.right == null) {
target.right = p;
} else {
placeNode(p, target.right);
}
}

}

private static void display(Node target) {
//Check if the node has left node
if (target.left != null) {
//if left node is present call display with left node as target
display(target.left);
}

//Print the data when left is null
System.out.println(target.data);

if (target.right != null) {
//if right node is present call display with right node as target
display(target.right);
}

}
}

```

Custom implementation of Collections and Data Structure:
Java Custom ArrayList