Java – How to Create Binary Search Tree for String Search

This article represents code samples and high level concepts for creating a binary search tree to do String related operations such as some of the following:

• Search one or more words
• Replace word with new word
• Find number of occurences of a given word in a string

For those who are new to Binary Search Tree, note that Binary Search Tree is defined as tree that satisfy some of the following criteria:

• Each node in the tree has at most only two children
• Each node is represented with a key and associated data
• Key in left children is less than the parent node and key in the right node is greater.
• Each node is in itself a binary search tree.

Please feel free to comment/suggest if I missed to mention one or more important points. Also, sorry for the typos.

Code Example – Create Binary Search Tree for String Search

Pay attention to some of the following:

• For inserting node, String is compared using compareTo function
• String is stripped off the punctuations. The stripped String is split into an array of word and then, each word is inserted into the tree.

public class BinaryStringTree {

 private String data;
 private BinaryStringTree left;
 private BinaryStringTree right;

 public BinaryStringTree() {
  this.data = null;
  this.left = null;
  this.right = null;
 }
 
 public BinaryStringTree(String data) {
  this.data = data;
  this.left = null;
  this.right = null;
 }

 public static BinaryStringTree createTree( String content ) {
  BinaryStringTree bstree = new BinaryStringTree();
  if( content != null ) {
   //
   // Remove the punctuation from the content
   //
   content = content.replaceAll("(\\w+)\\p{Punct}(\\s|$)", "$1$2");
   String[] words = content.split( " " );
   bstree = new BinaryStringTree();
   for( int i = 0; i < words.length; i++ ) {
    bstree.addNode( words[i] );
   }
  } 
  return bstree;
 }

 
 // As a convention, if the key to be inserted is less than the key of root
 // node, then key is inserted in
 // left sub-tree; If key is greater, it is inserted in right sub-tree. If it
 // is equal, as a convention, it
 // is inserted in right sub-tree
 public void addNode(String data) {
  if (this.data == null) {
   this.data = data;
  } else {
   if (this.data.compareTo(data) < 0) {
    if (this.left != null) {
     this.left.addNode(data);
    } else {
     this.left = new BinaryStringTree(data);
    }

   } else {
    if (this.right != null) {
     this.right.addNode(data);
    } else {
     this.right = new BinaryStringTree(data);
    }

   }
  }
 }
 
 public void traversePreOrder() {
  System.out.println(this.data);
  if (this.left != null) {
   this.left.traversePreOrder();
  }
  if (this.right != null) {
   this.right.traversePreOrder();
  }
 }

 public void traverseInOrder() {
  if (this.left != null) {
   this.left.traverseInOrder();
  }
  System.out.println(this.data);
  if (this.right != null) {
   this.right.traverseInOrder();
  }
 }


 public void traversePostOrder() {
  if (this.left != null) {
   this.left.traversePostOrder();
  }
  if (this.right != null) {
   this.right.traversePostOrder();
  }
  System.out.println(this.data);
 }

}