Binary search tree in java

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Binary search tree is a special type of binary tree which have following properties.

  • Nodes which are smaller than root will be in left subtree.
  • Nodes which are greater than root will be right subtree.
  • It should not have duplicate nodes
  • Both left and right subtree also should be binary search tree.
Example of binary search tree:
Lets perform following operation on binary search tree
  • Find
  • Insert

Search()

Searching a node in binary search is very easy. You just need to traverse left (if smaller) and right (if greater) according to value to be found.

Algorithm:

  • If node to be found is equal to root, then search is successful
  • If node to be found is smaller than root , then traverse left subtree.
  • If node to be found is greater than root, then traverse right subtree
  • Repeat above steps recursively until you find the node.
Search node in Binary search tree

Insert()

Insert node operation is also easy operation. You just need to compare it with root and traverse left (if smaller) or right(if greater) according to value of node to be inserted.

Algorithm:

  • Make root node as current node
  • If node to be inserted < root
    • If it has left child then traverse left
    • If it do not have left child, insert node here
  • If node to be inserted > root
    • If it have right child, traverse right
    • If it do not have right child, insert node here.
Insert node in binary search tree

Complete java program:

When you run above program, you will get below output:

Add Comment