Categories: JavaWeb

Java – How to Create a Binary Search Tree

This article represents the high level concept and code samples which could be used to create a binary search tree in Java. Please feel free to comment/suggest if I missed to mention one or more important points. Also, sorry for the typos.
Following are the key points described later in this article:
  • What is a binary search tree?
  • What are different kind of traversals?
  • Code Samples
What is a binary search tree?

A binary search tree is a binary tree in which every node contains a key that satisfies following criteria:

  • The key in left child is less than the key in the parent node
  • The key in the right child is more than the parent node
  • The left and right child are again binary search trees.

Following diagram represents a binary search tree:

What are different kind of traversals?

Following are three different kind of traversals:

  • Preorder traversal: In preorder traversal, the node is visted first and then, left and right sub-trees.
  • Inorder traversal: In inorder traversal, the node is visited between left and right sub-tree.
  • Postorder traversal: In postorder traversal, the node is visited after left and right subtrees.

 

Code Sample – How to Create a Binary Search Tree

If the numbers such as {20, 15, 200, 25, -5, 0, 100, 20, 12, 126, 1000, -150} are to be stored in a BinaryTree (represented by code below), following would get printed using different kind of traversal mechanism:

  //Preorder traversal
  20, 15, -5, -150, 0, 12, 200, 25, 20, 100, 126, 1000

  // Inorder traversal
  -150, -5, 0, 12, 15, 20, 20, 25, 100, 126, 200, 1000

  //Postorder traversal
  -150, 12, 0, -5, 15, 20, 126, 100, 25, 1000, 200, 20

Following is the code for creating binary tree that uses following BinaryTree class and traversals:

  BinaryTree tree = new BinaryTree( 20 );
  int[] nums = {15, 200, 25, -5, 0, 100, 20, 12, 126, 1000, -150};
  for(int i : nums ) {
   tree.addNode( i );
  }
  
  tree.traversePreOrder();
  tree.traverseInOrder();
  tree.traversePostOrder();

Following is the code for BinaryTree class:

 public class BinaryTree {

 private int data;
 private BinaryTree left;
 private BinaryTree right;

 public BinaryTree(int num) {
  this.data = num;
  this.left = null;
  this.right = null;
 }
 // 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(int num) {
  if (num < this.data) {
   if (this.left != null) {
    this.left.addNode(num);
   } else {
    this.left = new BinaryTree(num);
   }

  } else {
   if (this.right != null) {
    this.right.addNode(num);
   } else {
    this.right = new BinaryTree(num);
   }

  }
 }
 // Visit the node first, then left and right sub-trees
 public void traversePreOrder() {
  System.out.println( this.data );
  if( this.left != null ) {
   this.left.traversePreOrder();
  }
  if( this.right != null ) {
   this.right.traversePreOrder();
  }
 }
 // Visit left sub-tree, then node and then, right sub-tree
 public void traverseInOrder() {
  if( this.left != null ) {
   this.left.traverseInOrder();
  }
  System.out.println( this.data );
  if( this.right != null ) {
   this.right.traverseInOrder();
  }
 }
 // Visit left sub-tree, then right sub-tree and then the node
 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.

Recent Posts

Agentic Reasoning Design Patterns in AI: Examples

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

1 month ago

LLMs for Adaptive Learning & Personalized Education

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

2 months ago

Sparse Mixture of Experts (MoE) Models: Examples

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

2 months ago

Anxiety Disorder Detection & Machine Learning Techniques

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

2 months ago

Confounder Features & Machine Learning Models: Examples

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

2 months ago

Credit Card Fraud Detection & Machine Learning

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

2 months ago