Java Program to delete a node from Binary Search Tree(BST)

      In previous post, discussed about leaf node and total node count of BST. In this post, we will see how to delete a node from binary search tree.

      There are three scenario which we may need to consider while deleting a node from Binary Tree.

• If node has no child(i.e leaf node)
• If node has one child.
• If node has two children.

1) If node has no child(i.e leaf node)

       It is easy and straight forward, Just We need to search the node and make it null.

Example:--

2) If node has one child

     If node have one children then we need to connect parent of removed node directly to child of the removed node.

Example:-

3)  If node has two children

     It is somewhat complicated to delete the node.  If it has two nodes, we need to connect parent of node to the leftmost node(minimum) of right sub tree or rightmost node(maximum) of left sub tree.

Example:--

Java Program to Delete the Node from a Binary Tree.

BSTDeleteNode.java

package com.test;

class Node {
     

     Integer data;
     Node leftChild;
     Node rightChild;
 
     public Node(Integer data) {
           this.data = data;
           leftChild = null;
           rightChild = null;
     }
}

public class BSTDeleteNode {
 
       Node root;

       Node deleteNode(Integer data) {
            return deleteNode(root, data);
       }
       Node deleteNode(Node node, Integer data) {
            if (node == null) 
                 return node;
            if (data < node.data) {
                 node.leftChild = deleteNode(node.leftChild, data);
            } else if(data > node.data) {
                 node.rightChild = deleteNode(node.rightChild, data);
            } else {
                //node with only one child or no child
                 if (node.leftChild == null) {
                       return node.rightChild;
                 } else if(node.rightChild == null) {
                       return node.leftChild;
                 }
                 //node with two children, smallest in the right subtree
                 node.data = minValue(node.rightChild);
   
                 node.rightChild = deleteNode(node.rightChild, node.data);
   
           }
  
           return node;
      }
 
      int minValue(Node root) {
            int minv = root.data;
            while (root.leftChild != null) {
                minv = root.leftChild.data;
                root = root.leftChild;
            }
            return minv;
       }
 

       /*  To Print the given Node data

       */
       void inorderRec() {
             inorderRec(root);
       }
 
       void inorderRec(Node root) {
             if (root != null) {
                  inorderRec(root.leftChild);
                  System.out.print(root.data + " ");
                  inorderRec(root.rightChild);
             }
        }
 
        public static void main(String[] args) {
  
                BSTDeleteNode tree = new BSTDeleteNode();
                tree.root = new Node(10);
                tree.root.leftChild = new Node(6);
                tree.root.rightChild = new Node(16);
                tree.root.leftChild.leftChild = new Node(4);
                tree.root.leftChild.rightChild = new Node(8);
                System.out.println("Printing node before delete,");
                tree.inorderRec();
                tree.deleteNode(16);      //delete node method
                System.out.println("");
                System.out.println("Printing node after delete,");
                tree.inorderRec();
       }
}

Output :-
Printing node before delete,
4 6 8 10 16
Printing  node after delete,
4 6 8 10



Related Post:--
1) Java Program to Count the number of nodes and leaf nodes of Binary Tree
2) Java Program to Reverse a Linked List using Recursion and Loops
3) How to Remove duplicates from ArrayList in Java
4) Java Program to Count Occurrence of Word in a Sentence
5) How to iterate the TreeMap in reverse order in Java

Java Program to Count the number of nodes and leaf nodes of Binary Tree

           In a Binary Tree, each node can have at most two nodes. For a binary tree to be a binary search tree (BST), the data of all the nodes in the left sub-tree of the root node should be less than or equals to the data of the root. The data of all the nodes in the right sub tree of the root node should be greater than the data of the root.

Count the total number of Nodes using recursion.

The counts in the above tree is 5.

Java Program to Count  number of nodes in Binary Tree

BSTNodeCount.java

package com.test;

class Node<T> {
      T data;
      Node<T> leftChild;
      Node<T> rightChild;
 
      public Node(T item) {
           this.data = item;
           leftChild = null;
           rightChild = null;
     }
}

public class BSTNodeCount<T> {
 
      Node<T> root;
      int count = 0;

      int getNodeCount() {

           return getNodeCount(root);
      }

      int getNodeCount(Node<T> node) {
           if (node == null) {
                return 0;
           } else {
                count = 1;
                count+= getNodeCount(node.leftChild);
                count+= getNodeCount(node.rightChild);
           }
           return count;
      }
 

      public static void main(String[] args) {
  
             BSTNodeCount<Integer> tree = new BSTNodeCount<Integer>();
             tree.root = new Node<Integer>(10);
             tree.root.leftChild = new Node<Integer>(2);
             tree.root.rightChild = new Node<Integer>(15);
  
             System.out.println("Total Number of nodes in a BST :-"+tree.getNodeCount());
      }
}

Output:-- Total Number of nodes in a BST :-3


What is Leaf Node ?

Leaf Node is a node having both left and right child nodes of it are NULL.

In the above Tree, Nodes 5, 8 and 14 doesn't have left and right child nodes. There are 3 leaf nodes in the given BST.


Java Program to Count the number Leaf Nodes in the given Binary Tree.

package com.test;

class Node<T> {
      T data;
      Node<T> leftChild;
      Node<T> rightChild;
 
      public Node(T item) {
           this.data = item;
           leftChild = null;
           rightChild = null;
     }
}
public class BSTLeafNodeCount<T> {

       Node<T> root;
       int getLeafNodeCount() {
             return getLeafNodeCount(root);
       }
 
       int getLeafNodeCount(Node<T> node) {
            if(node == null) {
                 return 0;
            } 
            if (node.leftChild == null && node.rightChild == null) {
                 return 1;
            } else {
                 return getLeafNodeCount(node.leftChild) + getLeafNodeCount(node.rightChild);
            }
       }
 
       public static void main(String[] args) {

              BSTLeafNodeCount<Integer> tree = new BSTLeafNodeCount<Integer>();
              tree.root = new Node<Integer>(1);
              tree.root.rightChild = new Node<Integer>(2);
              tree.root.leftChild = new Node<Integer>(5);
              tree.root.rightChild.leftChild = new Node<Integer>(1);
  
              System.out.println("Total Number of Leaf Nodes in a BST:-"+tree.getLeafNodeCount());
       }
}

Total Number of Leaf Nodes in a BST:-2




Related Post:--
1) Java Program to Reverse a Linked List using Recursion and Loops
2) How to iterate the TreeMap in reverse order in Java
3) Example to sort keys of TreeMap using Comparator with Custom Object
4) Java Program to Count Occurrence of Word in a Sentence
5) How to Remove duplicates from ArrayList in Java

Hibernate - JPA Annotations with explanation

             In this post, we can learn some important Hibernate - JPA Annotations.  The following are the main Annotations which are used in the Hibernate.  For Spring annotations, Refer this Spring Annotations. 


 1) @Entity

     Annotate all your entity beans with @Entity. This contains in the javax.persistence package. 

@Entity
public class Employee implements Serializable {
  //properties with setters and getters
}

2) @Table
      The @Table annotation allows you to specify the details of the table that will be used to persist the entity in the database.

       The @Table annotation provides four attributes, allowing you to override the name of the table,  its catalog,  and its schema, and enforce unique constraints on columns in the table.

@Entity
@Table(name = "employee")
public class Employee implements Serializable {
     //properties with setters and getters
}

3) @Column

        The @Column annotation is used to specify the details of the column to which a field or property will be mapped.

      You can use column annotation with the following most commonly used attributes,

• name - attribute permits the name of the column to be explicitly specified.
• length - attribute permits the size of the column used to map a value particularly for a String value
• nullable - attribute permits the column to be marked NOT NULL when the schema is generated
• unique - attribute permits the column to be marked as containing only unique values.

@Entity
@Table(name = "employee")
public class Employee implements Serializable {
 
     @Column(name = "emp_name")
     private String name;
   
...
}

4) @Id

             This annotation specifies that a field is mapped to a primary key column in the table.
Since the column emp_id is a primary key,  we have to use this annotation as follows,

@Entity
@Table(name = "employee")
public class Employee implements Serializable {
 
     @Id
     @Column(name = "emp_id")
     private int empId;
   
...
}

5) @GeneratedValue

           If the values of the primary column are auto-increment, we need to use this annotation to tell Hibernate knows, along with one of the following strategy types: AUTO, IDENTITY, SEQUENCE, and TABLE. 
           In below example, strategy AUTO implies that the generated values are unique at database level.

@Entity
@Table(name = "employee")
public class Employee implements Serializable {
 
     @Id
     @GeneratedValue(strategy = GenerationType.AUTO)
     @Column(name = "emp_id", updatable = false, nullable = false)
   
...
}

6)  @OrderBy


   The @OrderBy orders the column values and put into the list as ordered list data. By Default @OrderBy orders the element in ascending order. We need to define property name on the basis of which values will be ordered.

@Entity
@Table(name = "employee")
public class Employee implements Serializable {
 
       @OneToMany(cascade=CascadeType.ALL)
       @JoinColumn(name="address_id")
       @OrderBy("name")
       private List<Address> address;
   
...
}

Hibernate Association Mapping Annotations

7)  @OneToOne

      The @OneToOne annotation is using for mapping between two tables that should be One To One mapping. 
      The below example illustrates the OneToOne Mapping between Employee and Department Entity.

Employee.java

@Entity
@Table(name = "employee")
public class Employee implements Serializable {
   
     @Id
     @Column(name = "emp_id")
     @GeneratedValue
     private int id;
   
     @Column(name="emp_name")
     private String name;

     @OneToOne(cascade=CascadeType.ALL)  
     @JoinColumn(name="dept_id")
     private Department department;
   
     // setters and getters
}
 

Department.java

@Entity
@Table(name = "department")
public class Department implements Serializable {
   
     @Id
     @Column(name = "dept_id")
     @GeneratedValue
     private int id;
   
     @Column(name="dept_name")
     private String name;

     @OneToOne(mappedBy="department")  
     private Employee employee;
   
     // setters and getters
}
 

8) @ManyToOne

    The below example illustrates the  ManyToOne Mapping between Employee and Address Entity.  One Employee can have multiple addresses.

Address.java

@Entity
@Table(name = "address")
public class Address implements Serializable {
   
     @Id
     @Column(name = "address_id")
     @GeneratedValue
     private int id;
   
     @Column(name="add_type")
     private String type;

     @ManyToOne
     @JoinColumn(name="emp_id") 
     private Employee employee;
   
     // setters and getters
}
 

9) @OneToMany

     It's opposite to @ManyToOne. The previous example, One employee can have multiple address so mapping should be OneToMany as below.

Employee.java

@Entity
@Table(name = "employee")
public class Employee implements Serializable {
   
     @Id
     @Column(name = "emp_id")
     @GeneratedValue
     private int id;
   
     @Column(name="emp_name")
     private String name;

     @OneToMany(mappedBy="employee") 
     private Set<Address> address;
   
     // setters and getters
}
 

10) @ManyToMany

It's example of Student and Department association.  Many students mapped with many departments using std_id and dept_id.

Student.java

@Entity
@Table(name = "student")
public class Student {
    
     @Id 
     @GeneratedValue
          (strategy = GenerationType.IDENTITY)
     @Column(name="std_id")
     private int id;

     @Column(name"std_name")
     private String name;

     @ManyToMany 
     @JoinTable(name="student_dept",  
      joinColumns = @JoinColumn(name="std_id"),
      inverseJoinColumns = @JoinColumn(name="dept_id"))  
     private Collection<Department> departments;

    // Setters and getters
    ....
}

Department.java

@Entity
@Table (name="student_dept")
public class Department {
     
     @Id 
     @GeneratedValue (strategy=GenerationType.IDENTITY)
     @Column(name="dept_id")
     private int id;
     
     @Column(name="dept_name")
     private String name;

     @ManyToMany(mappedBy="departments")
     private Collection<Student> students;

     // Setters and getters
     ...
}

Related Post:
1) Advantages of Hibernate over JDBC
2) What are the Core Interfaces of Hibernate framework ?
3) Spring MVC with Hibernate CRUD Example

Java Program to Reverse a Linked List using Recursion and Loops

           In previous post, we learned about Internal working of LinkedList in Java. In this, we can write a code to reverse a linkedlist using recursion and iterative way.

ReverseLinkedList.java:--

 package com.practice;

 public class ReverseLinkedList {
       static Node head;
  
       static class Node {
  
             int data;
             Node next;
  
             Node(int d) {
                 data = d;
                 next = null;
             }
        }
  
        // using iterative way
        Node reverse(Node node) {
             Node prev = null;
             Node current = node;
             Node next = null;
             while (current != null) {
                  next = current.next;
                  current.next = prev;
                  prev = current;
                  current = next;
             }
             node = prev;
             return node;
        }
    
        // using recursive
        Node reverseUtil(Node curr, Node prev) {
             if (curr.next == null) {
                  head = curr;
  
                  curr.next = prev;
                  return null;
              }
  
              Node next1 = curr.next;
  
               /* and update next ..*/
              curr.next = prev;
  
              reverseUtil(next1, curr);
              return head;
        }
  
         // prints content of linked list
        void printList(Node node) {
              while (node != null) {
                  System.out.print(node.data + " ");
                  node = node.next;
              }
         }
  
         public static void main(String[] args) {
                  ReverseLinkedList list = new ReverseLinkedList();
                  list.head = new Node(1);
                  list.head.next = new Node(2);
                  list.head.next.next = new Node(3);
                  list.head.next.next.next = new Node(4);
       
  
                  System.out.println("Original Linked list ");
                  list.printList(head);
                  Node res = list.reverseUtil(head, null);
                  System.out.println("");
                  System.out.println("Reversed linked list ");
                  list.printList(res);
      
                  System.out.println("");
                  System.out.println("Original Linked list2 ");
                  list.printList(head);
                  Node result = list.reverse(head);
                  System.out.println("");
                  System.out.println("Reversed linked list2 ");
                  list.printList(result);
        }
 }

Output:--   Original Linked list
                   1 2 3 4
                   Reversed linked list
                   4 3 2 1
                   Original Linked list2
                   4 3 2 1
                   Reversed linked list2
                   1 2 3 4


Related Post:--
1) Internal Implementation of LinkedList in Java
2) Internal implementation of ArrayList in Java
3) Java Program for Bubble Sort in Ascending and Descending order
4) Java Program to Sort ArrayList of Custom Objects By Property using Comparator interface
5) How to Remove duplicates from ArrayList in Java