Binary Search Tree in Java

Question

Please give me some feedback on how I could make it better or simpler.

public class BinarySearchTree {
 private static TreeNode root;
 public static void main(String args[]) {
 BinarySearchTree bst = new BinarySearchTree();
 root = bst.addItem(root, 10);
 bst.addItem(root, 2);
 bst.addItem(root, 6);
 bst.addItem(root, 3);
 bst.addItem(root, 1);
 bst.addItem(root, 15);
 bst.addItem(root, 12);
 bst.addItem(root, 16);
 System.out.println("** Print BST PRE ORDER **");
 bst.printPreOrderTree(root);
 System.out.println("** Print BST IN ORDER **");
 bst.printInOrderTree(root);
 System.out.println("** Print BST POST ORDER **");
 bst.printPostOrderTree(root);
 }
 private TreeNode addItem(TreeNode root, int item) {
 if (root == null) {
 root = new TreeNode(null, item, null);
 return root;
 } else {
 if (item < root.element) {
 if (root.left == null) {
 TreeNode node = addItem(root.left, item);
 root.left = node;
 } else {
 addItem(root.left, item);
 }
 } else if (item > root.element) {
 if (root.right == null) {
 TreeNode node = addItem(root.right, item);
 root.right = node;
 } else {
 addItem(root.right, item);
 }
 } else {
 System.out.println("Duplicate Item");
 }
 }
 return root;
 }
 private void printPreOrderTree(TreeNode root) {
 if (root != null) {
 System.out.println(root.element);
 printPreOrderTree(root.left);
 printPreOrderTree(root.right);
 }
 }
 private void printInOrderTree(TreeNode root) {
 if (root != null) {
 printInOrderTree(root.left);
 System.out.println(root.element);
 printInOrderTree(root.right);
 }
 }
 private void printPostOrderTree(TreeNode root) {
 if (root != null) {
 printPostOrderTree(root.left);
 printPostOrderTree(root.right);
 System.out.println(root.element);
 }
 }
 private static class TreeNode {
 TreeNode left;
 int element;
 TreeNode right;
 protected TreeNode(TreeNode left, int element, TreeNode right) {
 this.left = left;
 this.element = element;
 this.right = right;
 }
 }
}

Answer 1

static vs instance

Your variable root should probably not be static. Instead, it should be an instance variable so you could have multiple BinarySearchTrees in a single program.

node vs root

In most places, your naming of node vs root is good. In some places, I found it a bit misleading: In printPreOrderTree(), printInOrderTree() and printPostOrderTree() I'd rather call it node than root. I'd use root only for that type of node for which the system has no parent.

element vs item (vs data?)

I think you can get rid of one of these terms and only use the other. I'd use item and dismiss element. I find element too abstract, the term could also be a supertype of node. I think item describes the payload of a node better than element. But then again, maybe simply data would be even better?

Simpler Code in addItem()

Since you don't need to remember the variables, you can simplify the code.

Your code:

private TreeNode addItem(TreeNode root, int item) {
 if (root == null) {
 root = new TreeNode(null, item, null);
 return root;
 } else {
 if (item < root.element) {
 if (root.left == null) {
 TreeNode node = addItem(root.left, item);
 root.left = node;
 } else {
 addItem(root.left, item);
 }
 } else if (item > root.element) {
 if (root.right == null) {
 TreeNode node = addItem(root.right, item);
 root.right = node;
 } else {
 addItem(root.right, item);
 }
 } else {
 System.out.println("Duplicate Item");
 }
 }
 return root;
}

Simplified code:

private TreeNode addItem(TreeNode root, int item) {
 if (root == null)
 return new TreeNode(null, item, null);
 else if (item < root.element)
 if (root.left == null)
 root.left = addItem(root.left, item);
 else
 addItem(root.left, item);
 else if (item > root.element)
 if (root.right == null)
 root.right = addItem(root.right, item);
 else
 addItem(root.right, item);
 else
 System.out.println("Duplicate Item");
 return root;
}

And since the recursive addItem() is called anyway and checking root for null anyway, it can be even simpler:

private TreeNode addItem(TreeNode root, int item) {
 if (root == null)
 return new TreeNode(null, item, null);
 else if (item < root.element)
 root.left = addItem(root.left, item);
 else if (item > root.element)
 root.right = addItem(root.right, item);
 else
 System.out.println("Duplicate Item");
 return root;
}

Use stderr instead of stdout for error messages

Your error message

 System.out.println("Duplicate Item");

should not go to stdout but to stderr, I guess.

 System.err.println("Duplicate Item");

Use the Visitor pattern?

In printPreOrderTree, printInOrderTree and printPostOrderTree, you always visit all nodes.

The recursion over the nodes is always the same. What differs is the event placement and the action.

If your code gets more complex and you have more such recursions over the tree, you might want to use the Visitor design pattern to separate the recursion from the action to be performed with the node.

Answer 2

Just a tiny note: Your

 if (root.left == null) {
 TreeNode node = addItem(root.left, item);
 root.left = node;
 } else {
 addItem(root.left, item);
 }

is a bit confusing as you're passing root.left which you know is null. As pointed in the other answer, the local variable adds no value.

So I'd go for

 if (root.left == null) {
 root.left = addItem(root.left, item);
 } else {
 addItem(root.left, item);
 }

---

But I guess that just

 root.left = addItem(root.left, item);

without any conditions should work as well (in case root.left is not null, the assignment does nothing). This may cost a little speed, but without a need for optimizations, I'd go for it.