Binary Search Tree in Java, easy in 5 minutes

This post introduces about Binary Search Tree in Java, both of concept and implementation. Binary Search Tree is a binary tree data structure allows us to maintain a sorted list of numbers. Let’s dig deeper.

Binary Search Tree in Java

Properties of Binary Search Tree
  • The left subtree of a node has only nodes with keys lesser than its data.
  • The right subtree of a node has only nodes with keys greater than its data.
  • The left and right subtree must be a binary search tree too and there are no duplicate nodes.
Binary Search Tree
Binary Search Tree

Advantages: as you see the above image of Binary Search Tree. There is an ordering among nodes so that some operations can be done fast like search, minimum and maximum.

Searching a node in binary search tree

Now, I suppose that we are searching for a node with a given data. First, we must compare its data with the root node’s data. If the root contains that given data we return root. If the root node’s data is greater than that given data. We recur for the left subtree of the root node. Otherwise, we recur for the right subtree. Let’s have a look at the below implementation.

Insert a node in binary search tree

Inserting a value in the correct position is similar to searching because we must maintain the rule that left subtree is lesser than root and right subtree is larger than root. You certainly start from root till you hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node. And a new node is always inserted at leaf.

A complete implementation of Binary Search Tree in Java

This program demonstrates both the searching and insertion methods above.

Here is the output of the above program

That’s all about Binary Search Tree in Java.

References

Binary Tree Data Structure in Java


Binary Tree Java Documentation

Please share it if you found this useful
Hide Buttons