Binary search tree implementation (with Node class)

Question

I have implemented the Binary Search Tree in Java and would love to get reviews. I would like to have some comments on multi thread implantation.

Note: Corrected Code is in the Answers

package com.atleyvirdee.myDataStructures.tree.binarytree;

import com.atleyvirdee.myDataStructures.tree.ITree;
import com.atleyvirdee.myDataStructures.tree.ITreeNode;
import com.atleyvirdee.myDataStructures.tree.DFTreeTraverser;

@SuppressWarnings ( {"rawtypes", "unchecked"} )
public class BinaryTree implements ITree {

  private ITreeNode    root;
  public DFTreeTraverser treeTraverser = new DFTreeTraverser(root);

  @Override
  public void insert( Comparable data ) {
    root = insert(data, root);
  }

  @Override
  public void remove( Comparable data ) {
    if ( isEmpty() )
      System.out.println("Tree Empty");
    else if ( find(data) == null )
      System.out.println("Sorry " + data + " is not present");
    else {
      root = remove(data, root);
    }
  }

  @Override
  public void removeMin() {
    ITreeNode minimumNode = findMin(root);
    Comparable data = minimumNode.getData();
    remove(data);
  }

  @Override
  public Comparable find( Comparable data ) {
    ITreeNode dataNode = find(data, root);
    return (dataNode != null) ? dataNode.getData() : null;
  }

  @Override
  public Comparable findMin() {
    ITreeNode minimumNode = findMin(root);
    return minimumNode.getData();
  }

  @Override
  public Comparable findMax() {
    ITreeNode maximumNode = findMax(root);
    return maximumNode.getData();
  }

  @Override
  public boolean isEmpty() {
    return root == null ? true : false;
  }

  @Override
  public void makeEmpty() {
    this.root = null;
  }

  protected ITreeNode findMax( ITreeNode node ) {
    while (node.hasRightNode()) {
      node = node.getRightNode();
    }
    return node;
  }

  protected ITreeNode findMin( ITreeNode node ) {
    while (node.hasLeftNode()) {
      node = node.getLeftNode();
    }
    return node;
  }

  protected ITreeNode find( Comparable data, ITreeNode node ) {
    if ( node == null ) return null;
    if ( node.getData().compareTo(data) == 0 ) return node;
    if ( node.getData().compareTo(data) < 0 ) return find(data, node.getRightNode());
    return find(data, node.getLeftNode());
  }

  protected ITreeNode insert( Comparable data, ITreeNode node ) {
    ITreeNode n;
    if ( node == null ) {
      node = new BinaryTreeNode(data);
    } else if ( data.compareTo(node.getData()) < 0 ) {
      n = insert(data, node.getLeftNode());
      node.setLeftNode(n);
    } else if ( data.compareTo(node.getData()) > 0 ) {
      n = insert(data, node.getRightNode());
      node.setRightNode(n);
    } else {
      throw new RuntimeException("Data already in the Tree.");
    }
    return node;
  }

  protected ITreeNode remove( Comparable data, ITreeNode node ) {
    ITreeNode maxInLeftTree, newLeftChild, n;
    if ( node == null ) {
      return null;
    }
    if ( node.getData() == data ) {
      ITreeNode leftChild = node.getLeftNode();
      ITreeNode rightChild = node.getRightNode();
      if ( leftChild == null && rightChild == null ) // BOTH of the Child are null and Value
                                                     // matched.
        return null;
      else if ( leftChild == null ) {
        return rightChild;
      } else if ( rightChild == null ) {
        return leftChild;
      } else {
        maxInLeftTree = findMax(leftChild);
        Comparable value = maxInLeftTree.getData();
        newLeftChild = remove(value, leftChild);
        node.setData(value);
        node.setLeftNode(newLeftChild);
        return node;
      }
    }
    if ( data.compareTo(node.getData()) < 0 ) {
      n = remove(data, node.getLeftNode());
      node.setLeftNode(n);
    } else {
      n = remove(data, node.getRightNode());
      node.setRightNode(n);
    }
    return node;
  }

  @Override
  public DFTreeTraverser getTraverser() {
    treeTraverser.setRoot(root);
    return treeTraverser;
  }


  class BinaryTreeNode implements ITreeNode {

    ITreeNode  leftNode  = null;
    ITreeNode  rightNode = null;
    Comparable data      = null;

    public void setLeftNode( ITreeNode leftNode ) {
      this.leftNode = leftNode;
    }

    public void setRightNode( ITreeNode rightNode ) {
      this.rightNode = rightNode;
    }

    @Override
    public ITreeNode getLeftNode() {
      return this.leftNode;
    }

    @Override
    public ITreeNode getRightNode() {
      return this.rightNode;
    }

    @Override
    public Comparable getData() {
      return this.data;
    }

    @Override
    public boolean hasLeftNode() {
      return (this.leftNode != null) ? true : false;
    }

    @Override
    public boolean hasRightNode() {
      return (this.rightNode != null) ? true : false;
    }

    public BinaryTreeNode( Comparable data ) {
      this.data = data;
    }

    @Override
    public String toString() {
      return this.data.toString();
    }

    @Override
    public void setData( Comparable data ) {
      this.data = data;
    }
  }


  @Override
  public int size() {
    return size(root);
  }

  public int size(ITreeNode node) {

    int leftSize = 0,rightSize =0;

    if(node==null)
      return 0;

    if(node.hasLeftNode())
      leftSize = size(node.getLeftNode());

    if(node.hasRightNode())
      rightSize = size(node.getRightNode());

    return leftSize+rightSize+1;
  }

  @Override
  public ITreeNode getRoot() {
    return root;
  }



}

I've opted to rollback the question, see: What should I not do when someone answers my question. — h.j.k., Jul 13 '15 at 0:30
There's a "Posting a self-answer." section in the page I linked to, and generally nothing is stopping you from doing so. :) — h.j.k., Jul 13 '15 at 5:28

h.j.k. · Accepted Answer · 2015-06-16 16:06:34Z

First things first:

Generics

Your Comparable is missing it. And I suppose your custom classes are all missing it too. That explains why you are @Supress-ing "unchecked" warnings. I'm not sure if the root cause is because you are retro-fitting some older < Java 1.5 implementations or not, but for type safety please use generics. :)

Some other pointers:

@Override
public void insert( Comparable data ) {
  root = insert(data, root);
}

You probably want to update your treeTraverser here when you (potentially) re-assign your root.

@Override
public void remove( Comparable data ) {
    if ( isEmpty() )
      System.out.println("Tree Empty");
    else if ( find(data) == null )
      System.out.println("Sorry " + data + " is not present");
    else {
      root = remove(data, root);
    }
}

Inconsistent use of braces here, I'll suggest using it throughout.
Using System.out to do logging is a poor choice here, as the logging feature should be abstracted away to a logging framework. With that, you can optionally turn on/off messages on a per-level basis (e.g. DEBUG for development, but WARN for production), or even change the formatting.

@Override
public void removeMin() {
  ITreeNode minimumNode = findMin(root);
  Comparable data = minimumNode.getData();
  remove(data);
}

@Override
public Comparable findMin() {
    ITreeNode minimumNode = findMin(root);
    return minimumNode.getData();
}

Duplicated code. You can simply return findMin(root).getData(); from findMin(). Ditto for findMax().

protected ITreeNode findMax( ITreeNode node ) {
    while (node.hasRightNode()) {
      node = node.getRightNode();
    }
    return node;
}

Even though this is a very short method, I personally don't favor reassigning method arguments as it may get confusing as to what is being modified/assigned in the future, or for other longer methods. Ditto for findMin(ITreeNode). An alternative for writing the loop above may be:

protected ITreeNode findMax( ITreeNode node ) {
    for (ITreeNode current = node; current.hasRightNode(); 
            current = current.getRightNode()) {
        // empty
    }
    return current;
}

protected ITreeNode find( Comparable data, ITreeNode node ) {
    if ( node == null ) return null;
    if ( node.getData().compareTo(data) == 0 ) return node;
    if ( node.getData().compareTo(data) < 0 ) return find(data, node.getRightNode());
    return find(data, node.getLeftNode());
}

I'll suggest saving node.getData().compareTo(data) to a temporary variable and then operate on that:

protected ITreeNode find( Comparable data, ITreeNode node ) {
    if ( node == null ) {
        return null;
    }
    int result = node.getData().compareTo(data);
    return result == 0 ? node : 
            find(data, result < 0 ? node.getRightNode() : node.getLeftNode());
}

protected ITreeNode insert( Comparable data, ITreeNode node ) {
    ITreeNode n;
    if ( node == null ) {
      node = new BinaryTreeNode(data);
    } else if ( data.compareTo(node.getData()) < 0 ) {
      n = insert(data, node.getLeftNode());
      node.setLeftNode(n);
    } else if ( data.compareTo(node.getData()) > 0 ) {
      n = insert(data, node.getRightNode());
      node.setRightNode(n);
    } else {
      throw new RuntimeException("Data already in the Tree.");
    }
    return node;
}

You don't need the n temporary variable.
However, similar to the previous point, you may consider having a temporary variable to store the results of doing the compareTo().
Do you really want to throw an Exception for existing data? How about simply returning the Node unmodified?

Putting the suggestions together:

protected ITreeNode insert( Comparable data, ITreeNode node ) {
    if ( node == null ) {
        return new BinaryTreeNode(data);
    }
    int result = data.compareTo(node.getData());
    if ( result < 0 ) {
        node.setLeftNode(insert(data, node.getLeftNode()));
    } else if ( result > 0 ) {
        node.setRightNode(insert(data, node.getRightNode()));
    } else {
        // throw new RuntimeException("Data already in the Tree."); ?
    }
    return node;
}

remove() is kind of long to copy here so I'll just mention this: You have one inconsistent usage of braces.

@Override
public boolean hasLeftNode() {
    return (this.leftNode != null) ? true : false;
}

@Override
public boolean hasRightNode() {
    return (this.rightNode != null) ? true : false;
}

You don't need the ternary operator here, just do return leftNode != null or return rightNode != null respectively.

public int size(ITreeNode node) {

    int leftSize = 0,rightSize =0;

    if(node==null)
        return 0;

    if(node.hasLeftNode())
        leftSize = size(node.getLeftNode());

    if(node.hasRightNode())
        rightSize = size(node.getRightNode());

    return leftSize+rightSize+1;
}

You have pretty consistent and decent whitespacing... until here. You can probably shorten your code as such:

public int size(ITreeNode node) {
    if (node == null) {
        return 0;
    }
    return size(node.getLeftNode()) + size(node.getRightNode()) + 1;
}

Thanks buddy for your feedback. Will check my code for these and then will ask you questions. — Jaspinder Virdee, Jun 17 '15 at 3:17
I have Implemented the changes on the Code. Traverser root is already being changed in getTranverser Function. @Override public DFTreeTraverser<T> getTraverser() { treeTraverser.setRoot(root); return treeTraverser; } — Jaspinder Virdee, Jun 20 '15 at 19:33

Hurricane · Answer 2 · 2015-06-16 20:44:46Z

up vote 2 down vote

The only thing I could add is that the main interest of a binary search tree resides in the log(n) height. Without some re-balancing mechanism, in worst case, the tree will behave like a list. You may be interested in taking a look to AVL (they always have an optimal depth), Red-Black, ...

answered Jun 16 '15 at 20:44

Hurricane

42410

True. Well I have implemented self balancing binary tree in another class. Will share that too for the code review. This was my first tree implementation:) – Jaspinder Virdee Jun 17 '15 at 3:16

add a comment |

Jaspinder Virdee · Answer 3 · 2015-07-13 06:19:13Z

Following is the corrected code of above Question. Will update this if I get more answers.

package com.atleyvirdee.myDataStructures.tree.binarytree;

import com.atleyvirdee.myDataStructures.tree.ITree;
import com.atleyvirdee.myDataStructures.tree.ITreeNode;
import com.atleyvirdee.myDataStructures.tree.DFTreeTraverser;

public class BinaryTree<T extends Comparable<T>> implements ITree<T> {

  private ITreeNode<T>      root;
  public DFTreeTraverser<T> treeTraverser = new DFTreeTraverser<T>(root);

  @Override
  public void insert( T data ) {
    root = insert(data, root);
  }

  @Override
  public void remove( T data ) {
    if ( isEmpty() )
      System.out.println("Tree Empty");
    else if ( find(data) == null )
      System.out.println("Sorry " + data + " is not present");
    else {
      root = remove(data, root);
    }
  }

  @Override
  public void removeMin() {
    ITreeNode<T> minimumNode = findMin(root);
    T data = minimumNode.getData();
    remove(data);
  }

  @Override
  public T find( T data ) {
    ITreeNode<T> dataNode = find(data, root);
    return (dataNode != null) ? dataNode.getData() : null;
  }

  @Override
  public T findMin() {
    return findMin(root).getData();
  }

  @Override
  public T findMax() {
    return findMax(root).getData();
  }

  @Override
  public boolean isEmpty() {
    return root == null ? true : false;
  }

  @Override
  public void makeEmpty() {
    this.root = null;
  }

  protected ITreeNode<T> findMax( ITreeNode<T> node ) {
    ITreeNode<T> current = node;
    while (current.hasRightNode()) {
      current = current.getRightNode();
    }
    return current;
  }

  protected ITreeNode<T> findMin( ITreeNode<T> node ) {
    ITreeNode<T> current = node;
    while (current.hasLeftNode()) {
      current = current.getLeftNode();
    }
    return current;
  }

  protected ITreeNode<T> find( T data, ITreeNode<T> node ) {
    if ( node == null ) return null;
    int result = node.getData().compareTo(data);
    return result == 0 ? node : find(data, result < 0 ? node.getRightNode() : node.getLeftNode());
  }

  protected ITreeNode<T> insert( T data, ITreeNode<T> node ) {
    ITreeNode<T> n;
    if ( node == null ) {
      node = new BinaryTreeNode<T>(data);
      return node;
    }
    int result = data.compareTo(node.getData());
    if ( result < 0 ) {
      n = insert(data, node.getLeftNode());
      node.setLeftNode(n);
    } else if ( result > 0 ) {
      n = insert(data, node.getRightNode());
      node.setRightNode(n);
    } else {
      throw new RuntimeException("Data already in the Tree.");
    }
    return node;
  }

  protected ITreeNode<T> remove( T data, ITreeNode<T> node ) {
    ITreeNode<T> maxInLeftTree, newLeftChild, n;
    if ( node == null ) {
      return null;
    }
    if ( node.getData() == data ) {
      ITreeNode<T> leftChild = node.getLeftNode();
      ITreeNode<T> rightChild = node.getRightNode();
      if ( leftChild == null && rightChild == null ) // BOTH of the Child are null and Value
                                                     // matched.
        return null;
      else if ( leftChild == null ) {
        return rightChild;
      } else if ( rightChild == null ) {
        return leftChild;
      } else {
        maxInLeftTree = findMax(leftChild);
        T value = maxInLeftTree.getData();
        newLeftChild = remove(value, leftChild);
        node.setData(value);
        node.setLeftNode(newLeftChild);
        return node;
      }
    }
    if ( data.compareTo(node.getData()) < 0 ) {
      n = remove(data, node.getLeftNode());
      node.setLeftNode(n);
    } else {
      n = remove(data, node.getRightNode());
      node.setRightNode(n);
    }
    return node;
  }

  @Override
  public DFTreeTraverser<T> getTraverser() {
    treeTraverser.setRoot(root);
    return treeTraverser;
  }


  class BinaryTreeNode<E extends Comparable<E>> implements ITreeNode<E> {

    ITreeNode<E> leftNode  = null;
    ITreeNode<E> rightNode = null;
    E            data      = null;

    public void setLeftNode( ITreeNode<E> leftNode ) {
      this.leftNode = leftNode;
    }

    public void setRightNode( ITreeNode<E> rightNode ) {
      this.rightNode = rightNode;
    }

    @Override
    public ITreeNode<E> getLeftNode() {
      return this.leftNode;
    }

    @Override
    public ITreeNode<E> getRightNode() {
      return this.rightNode;
    }

    @Override
    public E getData() {
      return this.data;
    }

    @Override
    public boolean hasLeftNode() {
      return this.leftNode != null;
    }

    @Override
    public boolean hasRightNode() {
      return this.rightNode != null;
    }

    public BinaryTreeNode( E data ) {
      this.data = data;
    }

    @Override
    public String toString() {
      return this.data.toString();
    }

    @Override
    public void setData( E data ) {
      this.data = data;
    }
  }

  @Override
  public int size() {
    return size(root);
  }

  public int size( ITreeNode<T> node ) {
    if ( node == null ) return 0;
    return size(node.getLeftNode()) + size(node.getRightNode()) + 1;
  }

  @Override
  public ITreeNode<T> getRoot() {
    return root;
  }
}

asked	11 months ago
viewed	240 times
active	10 months ago

current community

your communities

more stack exchange communities

Binary search tree implementation (with Node class)

3 Answers 3

Your Answer

Not the answer you're looking for? Browse other questions tagged java algorithm tree binary-search or ask your own question.

Linked

Hot Network Questions

current community

your communities

more stack exchange communities

Binary search tree implementation (with Node class)

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged java algorithm tree binary-search or ask your own question.

Linked

Related

Hot Network Questions