BST insertion and in order traversal

Question

package com.goman;
public class BST {
 private BST left;
 private BST right;
 private int data;
 public BST(int data, BST left, BST right){
 this.left = left;
 this.right = right;
 this.data = data;
 }
 public BST insert(BST node, BST root){
 if(root == null){
 return node;
 }
 if(root.data > node.data){
 root.left = insert(node, root.left);
 } else if(root.data < node.data){
 root.right = insert(node, root.right);
 } else{
 System.out.println("Duplicate valuesa are not allowed");
 return root;
 }
 return root;
 }
 @Override
 public String toString() {
 return "BST [left=" + left + ",right=" + right + ",data=" + data
 + "]";
 }
 public void inOrder(BST root){
 if(root==null){
 return;
 }
 inOrder(root.left);
 System.out.println(root.data);
 inOrder(root.right);
 }
}
class Test{
 public static void main(String[] a){
 BST root = new BST(5, null, null);
 root.insert(new BST(3, null, null), root);
 root.insert(new BST(8, null, null), root);
 root.insert(new BST(2, null, null), root);
 root.insert(new BST(4, null, null), root);
 root.inOrder(root);
 System.out.println(root);
 }
}

Answer 1

Broken API

The class name BST suggests that it's a binary search tree, but it's not. It's a node (in a binary tree), with private references to other nodes.

If it's intended to be a node in a binary search tree, its API is broken. The insert method takes two parameters, both of them BST instances. It works fine when the first parameter is a BST instance without children (left and right nodes both null), but if you pass to it two nodes with children, the result will be no longer a binary search tree, for example:

BST root = new BST(5, null, null);
root.insert(new BST(3, null, null), root);
BST root2 = new BST(7, null, null);
root2.insert(new BST(3, null, null), root2);
root2.insert(root2, root);
root.inOrder(root);
System.out.println(root);

This will output:

3
5
3
7
BST [left=BST [left=null,right=null,data=3],right=BST [left=BST [left=null,right=null,data=3],right=null,data=7],data=5]

The result corresponds to this tree, which is not a binary search tree:

 5
 / \
3 7
 /
 3

You could avoid this by allowing to pass as parameter only data, not another BST instance.

Note that the constructor suffers from the same problem, because the left and right parameters to insert arbitrary BST instances with children, breaking the binary search tree property.

Strange API

The insert method doesn't use any fields or methods of the instance. It could have been a static method. It would have made more sense to use this method signature:

public void insert(int data) {

This method could use this.data, this.left, and this.right to perform inserting a new value, and it could successfully protect the binary search tree property.

The inOrder method has the same issue. I suggest to drop the BST argument.

After you rewrite the insert method this way, and also drop the dangerous left and right constructor parameters, the example code in your question will become simpler and more natural too:

BST root = new BST(5);
root.insert(3);
root.insert(8);
root.insert(2);
root.insert(4);
root.inOrder();
System.out.println(root);

Extension ideas

Instead of int as the data, you could make this class generic, by declaring as public class BST<T extends Comparable<T>>, and using type T everywhere instead of int, and rewriting x < y comparisons with x.compareTo(y) < 0.

Instead of inOrder printing data, you could allow a Consumer<T> argument, to let users decide what they want to do with the visited nodes. For example, if you rewrite inOrder like this:

public void inOrder(Consumer<T> consumer) {
 left.inOrder(consumer);
 consumer.accept(data);
 right.inOrder(consumer);
}

Then users could print the node values in in-order with:

root.inOrder(System.out::println);

toString value hard to read

The toString method returns this for the tree in your example:

BST [left=BST [left=BST [left=null,right=null,data=2],right=BST [left=null,right=null,data=4],data=3],right=BST [left=null,right=null,data=8],data=5]

This is hard to read, because the data is printed after the children. I suggest to print data before the children, and also the implementation maybe slightly easier to read using String.format:

return String.format("BST [data=%s,left=%s,right=%s]", data, left, right);