import java.util.Vector;

/** A data structure representing a node in a binary tree.
 *  It contains a node value and a reference (pointer) to
 *  the left and right subtrees.
 *
 *  Taken from Core Web Programming from 
 *  Prentice Hall and Sun Microsystems Press,
 *  http://www.corewebprogramming.com/.
 *  © 2001 Marty Hall and Larry Brown;
 *  may be freely used or adapted. 
 */

public class Node {
  private Object nodeValue;
  private Node leftChild, rightChild;

 /** Build Node with specified value and subtrees. */

  public Node(Object nodeValue, Node leftChild,
              Node rightChild) {
    this.nodeValue = nodeValue;
    this.leftChild = leftChild;
    this.rightChild = rightChild;
  }

  /** Build Node with specified value and L subtree. R child
   *  will be null. If you want both children to be null, use
   *  the Leaf constructor.
   */

  public Node(Object nodeValue, Node leftChild) {
    this(nodeValue, leftChild, null);
  }

  /** Return the value of this node. */

  public Object getNodeValue() {
    return(nodeValue);
  }

  /** Specify the value of this node. */

  public void setNodeValue(Object nodeValue) {
    this.nodeValue = nodeValue;
  }

 /** Return the L subtree. */

  public Node getLeftChild() {
    return(leftChild);
  }

  /** Specify the L subtree. */

  public void setLeftChild(Node leftChild) {
    this.leftChild = leftChild;
  }

  /** Return the R subtree. */

  public Node getRightChild() {
    return(rightChild);
  }

  /** Specify the R subtree. */

  public void setRightChild(Node rightChild) {
    this.rightChild = rightChild;
  }

  /** Traverse the tree in depth-first order, applying
   *  the specified operation to each node along the way.
   */

  public void depthFirstSearch(NodeOperator op) {
    op.operateOn(this);
    if (leftChild != null) {
      leftChild.depthFirstSearch(op);
    }
    if (rightChild != null) {
      rightChild.depthFirstSearch(op);
    }
  }

  /** Traverse the tree in breadth-first order, applying the
   *  specified operation to each node along the way.
   */

  public void breadthFirstSearch(NodeOperator op) {
    Vector nodeQueue = new Vector();
    nodeQueue.addElement(this);
    Node node;
    while(!nodeQueue.isEmpty()) {
      node = (Node)nodeQueue.elementAt(0);
      nodeQueue.removeElementAt(0);
      op.operateOn(node);
      if (node.getLeftChild() != null) {
        nodeQueue.addElement(node.getLeftChild());
      }
      if (node.getRightChild() != null) {
        nodeQueue.addElement(node.getRightChild());
      }
    }
  }
}