Binary Search Tree Data Structure

Binary Search Tree :

A data struc­ture in which we have nodes con­tain­ing data and two ref­er­ences to other nodes, one on the left and one on the right.

 Binary Tree con­sist of Nodes

  • Nodes are noth­ing but objects of a class and each node has data and a link to the left node and right node.
  • Usu­ally we call the start­ing node of a tree as root.
  •  Left and right node of a Leaf node points to NULL so you will know that you have reached to the end of the tree.

Binary Search Tree Diagram

Binary Search Tree Oper­a­tions:

Insert(int n) : Add a node the tree with value n. Its O(lgn) Find(int n) : Find a node the tree with value n. Its O(lgn) Delete (int n) : Delete a node the tree with value n. Its O(lgn) Dis­play(): Prints the entire tree in increas­ing order. O(n).

Detail Expla­na­tions for the Operations given below.

Insert(int n):
  • Very much sim­i­lar to find() operation.
  • To insert a node our first task is to find the place to insert the node.
  • Take cur­rent = root .
  • start from the cur­rent and com­pare root.data with n
  • if current.data is greater than n that means we need to go to the left of the root.
  • if current.data is smaller than n that means we need to go to the right of the root.
  • if any point of time cur­rent is null that means we have reached to the leaf node, insert your node here with the help of par­ent node. (See code)

Operational Diagram

Binary Search Tree implementation in Java Example-

/** 
Binary Tree Implementation in java with insert and traversing 
process step by step procedure
  */
package tree_impl;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
/** * @author namdeva
 *  */
public class Tree_Implementation extends Tree_Node {
    int count = 0;
    Tree_Node parent;
    Tree_Node root;
    Tree_Node current;
    List<Integer> list;
    public void insert(int data) {
        Tree_Node newNode = new Tree_Node();
        if (parent == null) {
            newNode.setData(data);
            parent = newNode;
        } else {
            root = parent;
            while (true) {
                current = root;
                if (data < root.getData()) {
                    root = root.getLeft_child();
                    if (root == null) {
                        newNode.setData(data);
                        current.setLeft_child(newNode);
                        root = newNode;
                        count++;
                        return;
                    }
                } else {
                    root = root.getRight_child();
                    if (root == null) {
                        newNode.setData(data);
                        current.setRight_child(newNode);
                        root = newNode;
                        count++;
                        return;
                    }
                }
            }
        }
    }

Traverse -

 public void traverse() {
        System.out.print("preOrder  : ");
        preOrder(parent);
        System.out.println("");
        System.out.print("postOrder : ");
        postOrder(parent);
        System.out.println("");
        System.out.print("inOrder   : ");
        inOrder(parent);
        System.out.println("");
    }

postOrder and preOrder -

public void preOrder(Tree_Node node) {
        if (node != null) {
            System.out.print(node.getData() + " ");
            preOrder(node.getLeft_child());
            preOrder(node.getRight_child());
        }
    }
    public void postOrder(Tree_Node node) {
        if (node != null) {
            postOrder(node.getLeft_child());
            postOrder(node.getRight_child());
            System.out.print(node.getData() + " ");
        }
    }

inOrder and find operation -

    public void inOrder(Tree_Node node) {
        if (node != null) {
            inOrder(node.getLeft_child());
            System.out.print(node.getData() + " ");
            inOrder(node.getRight_child());
        }
    }
    public boolean find(int data) {
        boolean flag = false;
        Tree_Node temp = parent;
        while (temp != null) {
            if (data < temp.getData()) {
                if (data == temp.getData()) {
                    flag = true;
                    return flag;
                }
                temp = temp.getLeft_child();
            } else {
                if (data == temp.getData()) {
                    flag = true;
                    return flag;
                }
                temp = temp.getRight_child();
            }
        }
        return flag;
    }

preOrder Traverse and inOrder Traverse -

    public void preOrderTraverse() {
        Tree_Node temp = parent;
        Stack<Tree_Node> st = new Stack<Tree_Node>();
        st.push(parent);
        System.out.print("preOrder  : ");
        while (true) {
            if (temp != null) {
                System.out.print(temp.getData() + " ");
                st.push(temp);
                temp = temp.getLeft_child();
            } else {
                temp = st.pop();
                temp = temp.getRight_child();
            }
            if (st.isEmpty()) {
                System.out.println("");
                return;
            }
        }
    }
    public void inOrderTraverse() {
        Tree_Node temp = parent;
        Stack<Tree_Node> st = new Stack<Tree_Node>();
        st.push(parent);
        System.out.print("inOrder   : ");
        while (true) {
            if (temp != null) {
                st.push(temp);
                temp = temp.getLeft_child();
            } else {
                temp = st.pop();
                if ((temp == parent) && (st.isEmpty() == true)) {
                    return;
                }
                System.out.print(temp.getData() + " ");
                temp = temp.getRight_child();
            }
            if (st.isEmpty()) {
                return;
            }
        }
    }

postOrder Traverse -

public void postOrderTraverse() {
        Stack<Tree_Node> st = new Stack<Tree_Node>();
        st.push(parent);
        System.out.println("");
        System.out.print("postOrder : ");
        Tree_Node prev = null;
        while (!st.isEmpty()) {
            Tree_Node curr = st.peek();
         if (prev == null || prev.getLeft_child() == curr || prev.getRight_child() == curr) {
                if (curr.getLeft_child() != null) {
                    st.push(curr.getLeft_child());
                } else if (curr.getRight_child() != null) {
                    st.push(curr.getRight_child());
                }
            } else if (curr.getLeft_child() == prev) {
                if (curr.getRight_child() != null) {
                    st.push(curr.getRight_child());
                }
            } else {
                System.out.print(curr.getData() + " ");
                st.pop();
            }
            prev = curr;
        }
    }
    public void BFS(){
        Queue<Tree_Node> q1 =new LinkedList<Tree_Node>();
        Queue<Tree_Node> q2 =new LinkedList<Tree_Node>();
        Tree_Node temp=parent;
        q1.offer(temp);
        System.out.println("");
        System.out.print("BFS       : ");
        System.out.print(temp.getData()+ " ");
        while(!(q1.isEmpty()) || !(q2.isEmpty())){
            while(q1!=null && !q1.isEmpty()){
                temp=q1.peek();
                if(temp.getLeft_child()!=null){
                q2.offer(temp.getLeft_child());
                System.out.print(temp.getLeft_child().getData() +" ");
                }
                if(temp.getRight_child()!=null){
                    q2.offer(temp.getRight_child());
                System.out.print(temp.getRight_child().getData() +" ");
            }
                q1.poll();
            }
            while(q2!=null && !q2.isEmpty()){
                temp=q2.peek();
                if(temp.getLeft_child()!=null){
                    q1.offer(temp.getLeft_child());
                    System.out.print(temp.getLeft_child().getData() +" ");
                }
                 if(temp.getRight_child()!=null){
                        q1.offer(temp.getRight_child());
                        System.out.print(temp.getRight_child().getData() +" ");
                    }
                 q2.poll();
            }
        }
    }
    public int findHeight() {
        int h=0;
        Tree_Node temp=parent;
       h= height(temp);
        return h;
    }
    public int height(Tree_Node root){
        if(root==null){
            return 0;
        }
        int left=height(root.getLeft_child());
        int right=height(root.getRight_child());
        return left>right?left+1:right+1;
    }
    public static void main(String args[]) {
        Tree_Implementation tree = new Tree_Implementation();
        tree.insert(10);
        tree.insert(8);
        tree.insert(6);
        tree.insert(9);
        tree.insert(13);
        tree.insert(11);
        tree.insert(14);
        tree.traverse();
        System.out.println(tree.find(15));
        tree.preOrderTraverse();
        tree.inOrderTraverse();
        tree.postOrderTraverse();
        tree.BFS();
        System.out.println(tree.findHeight());
    }
}
 

Leave a Comment

%d bloggers like this: