Java – How to Create Binary Search Tree for String Search

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

}