MCX2                                                                                                           Mr Stanley Teitel, Principal
Mr. Gary. Jaye                                                                                               Mr. Danny Jaye,  Math Chair

1995 APCS AB Exam: Question 4

Assume that binary trees are implemented using the following definitions. 

  public class  TreeNode {
     public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight) {...}
    public Object getValue() {...}
    public TreeNode getLeft() {...}
    public TreeNode getRight() {...}
    public void setValue(Object theNewValue) {...}
    public void setLeft(TreeNode theNewLeft) {...}
    public void setRight(TreeNode theNewRight) {...}
    < private data members >
}

part A 
Write function IsChild whose header is given below. IsChild returns true if the node pointed to
be parameter second is a child (either left or right) of the node pointed to be parameter first, and returns 
false otherwise. 

    public static boolean IsChild(TreeNode first, TreeNode second)
    // precondition: second != null
    // postcondition: returns true if second is a child of first; returns false otherwise

part B 
Write the function IsDescendant whose header is given below. IsDescendant returns true if there
is a path from the node pointed to by parameter first to the node pointed to by parameter second, 
where a path is a nonempty sequence of left or right children 

For example, consider the tree diagrammed below: 

          function call            value returned
      IsDescendant(NodeC, NodeA)     false 
      IsDescendant(NodeA, NodeB)     true
      IsDescendant(NodeB, NodeA)     false
      IsDescendant(NodeC, NodeD)     true
      IsDescendant(NodeA, NodeA)     false

In writing IsDescendant you may call function IsChild of part (a). Assume that IsChild works 
as specified, regardless of what you wrote in part A. 

Complete IsDescendant below the following header. 

public static boolean  IsDescendant(TreeNode first, TreeNode second)
 // precondition: second != null

part C
Write function ChangeTree, whose header is given below. ChangeTree removes from t 
all nodes that have exactly one child, replacing the removed node with the child. If A and B are 
nodes in t that do NOT have exactly one child, and if IsDescendant(A,B) is true before the call 
ChangeTree(t), then IsDescendent(A,B) must be true AFTER the call ChangeTree(t). You 
may assume that the root will have either no children or two children before the call. 

For example: 


In writing ChangeTree, you may call function HasOneChild, defined below. 

 static boolean  HasOneChild(TreeNode  t)  {
 // postcondition: returns true if t has exactly one child, else returns false
       if (t != null &&  (t.getLeft() == null && t.getRight() != null || t.getLeft() != null &&  t.getRight()  == null) )
                return true;
       else
               return false;
 }

Complete function ChangeTree below the following header. 

 public static void ChangeTree(TreeNode  t) {
 // precondition: the root never has one child