package binaryTree.visitor;

import binaryTree.*;
import ordering.*;

/**
 * Finds a data object in a binary host tree that satisfies the Binary Search Tree Property.
 * @author Dung X. Nguyen
 */
public class BSTFinder implements IVisitor
{
   private AOrder _order;

	public BSTFinder (AOrder order)
	{
      _order = order;
	}

	/**
    * Returns null.
	 * @param host an empty binary (which obviously satisfies the Binary Search Tree Property).
	 * @param input not used
	 */
	public Object emptyCase(BiTree host, Object input)
	{
		return null;
	}

	/**
    * Returns the tree whose root is equal to input via the ordering order, otherwise returns null.
	 * @param host satisfies BSTP.
	 * @param input object to be looked up.
	 * @return null or a BiTree object whose root is equal input (via order).
	 */
	public Object nonEmptyCase(BiTree host, Object input)
	{
      Object root = host.getRootDat();
      if (_order.lt (input, root))
      {
        return host.getLeftSubTree().execute (this, input);
      }
      if (_order.eq (input, root))
      {
         return host;
      }
      return host.getRightSubTree().execute (this, input);
	}
}