Binary Search Tree is a data structure in which the given tree is structured in such a way that the left child node is always less than the parent node and the parent node is always less than the right child node.
In this tutorial we will see how to store and retrieve data in BST.
First we create a node with data and left and right pointers which will help us store information about any given node's two children node.
public class Node {
public int element; // The data in the node
public Node left; // Left child
public Node right; // Right child
public Node(int element, Node left, Node right) {
this.element = element;
this.left = left;
this.right = right;
}
}
After this we will implement how to insert node in to a BST
public class MyBST {
/** The tree root. */
private Node root;
//--insert an element in the correct position---
public void insert(int x) {
if (root == null) {
root = new Node(x, null, null);
}
else {
Node n = root;
bool inserted = false;
while (!inserted) {
if (x < n.element ) {
//space found on the left
if (n.left == null) {
n.left = new Node(x, null, null);
inserted = true;
}
else {
n = n.left;
}
}
else if (x > n.element) {
//space found on the right
if (n.right == null) {
n.right = new Node(x, null, null);
inserted = true;
}
else {
n = n.right;
}
}
}
}
}
}
Let's understand what is going on here.
- Initially the BST is empty so we just create a new node and make left and right as null
- If there is an item already in the BST, then we will ask ourselves if the new number we want to insert is less than the root, if yes we will drill down to left by moving our reference to the left (n = n.Left). If in case we see that n.Left is null, then space is available for the new node and we can insert right there. (n.left = new Node()).
- Otherwise, we keep asking the same question we ask in the beginning and keep navigating down the tree based on whether data is less than or greater than the current node we are in .
We can also insert a node using the recursive method.
public void InsertByRecursion(int x, Node root) {
if (root == null) {
Node n = new Node(x, null, null);
root = n;
}
else {
if (x < root.element) {
if (root.left == null) {
Node n = new Node(x,null, null);
root.left = n;
}
else
InsertByRecursion(x, root.left);
}
else if (x > root.element) {
if (root.right == null) {
Node n = new Node(x,null,null);
root.right = n;
}
else
InsertByRecursion(x, root.right);
}
}
}
Now let see how to print the values in the nodes of the tree in sorted order(In order traversing) . That is left child first then parent and then right child.
public void printTree() {
if (root == null)
Console.WriteLine("Empty tree");
else
printTree(root);
}
private void printTree(Node t) {
if (t != null) {
printTree(t.left);
Console.WriteLine(t.element);
printTree(t.right);
}
}
As you can imagine, we use recursion here to print the left node first and then the parent and finally the right node.
Let's test it.
public static void Main(string[] args) {
MyBST bst = new MyBST();
bst.insert(9);
bst.insert(2);
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.printTree();
}
output: 2 3 4 5 9
This is how it should look like in a diagram.
9
2
3
4
5