Categories: JavaWeb

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);
 }

}


Ajitesh Kumar

I have been recently working in the area of Data analytics including Data Science and Machine Learning / Deep Learning. I am also passionate about different technologies including programming languages such as Java/JEE, Javascript, Python, R, Julia, etc, and technologies such as Blockchain, mobile computing, cloud-native technologies, application security, cloud computing platforms, big data, etc. I would love to connect with you on Linkedin. Check out my latest book titled as First Principles Thinking: Building winning products using first principles thinking.

View Comments

Recent Posts

Agentic Reasoning Design Patterns in AI: Examples

In recent years, artificial intelligence (AI) has evolved to include more sophisticated and capable agents,…

3 weeks ago

LLMs for Adaptive Learning & Personalized Education

Adaptive learning helps in tailoring learning experiences to fit the unique needs of each student.…

4 weeks ago

Sparse Mixture of Experts (MoE) Models: Examples

With the increasing demand for more powerful machine learning (ML) systems that can handle diverse…

1 month ago

Anxiety Disorder Detection & Machine Learning Techniques

Anxiety is a common mental health condition that affects millions of people around the world.…

1 month ago

Confounder Features & Machine Learning Models: Examples

In machine learning, confounder features or variables can significantly affect the accuracy and validity of…

1 month ago

Credit Card Fraud Detection & Machine Learning

Last updated: 26 Sept, 2024 Credit card fraud detection is a major concern for credit…

1 month ago