Other 2009 FR Questions FR other years Be Prepared Home
Part (a)
  /** Creates two new nodes that each contain the same value as contained in t.
   *  These new nodes become the left and right child nodes of t.
   *  The original left child of t becomes the left child of the new left child,
   *  and the original right child of t becomes the right child of the new right child.
   *  @param t a reference to the node to be expanded
   *          Precondition: t is not null
  private static void expandNode(TreeNode t)
    TreeNode left = new TreeNode(t.getValue(), t.getLeft(), null);
    TreeNode right = new TreeNode(t.getValue(), null, t.getRight());
    t.setLeft(left); 1
  1. Not
        t.getLeft() = left;
        t.getRight() = right;

Part (b)
  /** Grows the tree by expanding all nodes containing val in the subtree rooted at current
   *  @param current the root of the subtree to be processed
   *  @param val the value to be matched
  private static void growTreeHelper(TreeNode current, Object val)
    if (current != null)
      growTreeHelper(current.getLeft(), val);
      if (current.getValue().equals(val))

Part (c)

Method Big-Oh
expandNode O(1)
growTreeHelper O(n)

Other 2009 FR Questions | Back to Contents

Copyright © 2009 by Skylight Publishing