Solution for HW 1, CS 3114 Summer 2016 -------------------------------------------------------------------------------- For questions 1 through 4, refer to the BST generic interface provided for Minor Project 2. Strive for the most efficient solution you can devise. You may not use any Java collections, including ones you implement yourself, to store any additional information (like copying the data elements from the BST into an array). 1. [20 points] Design an algorithm to determine whether a given binary tree contains any single-child nodes; that is, nodes that have exactly one child. Express your solution using Java code as if it were to be implemented as a public member function (with private helper) belonging to the BST generic specified in Minor Project 2; your answer (which will include both the public and private functions) must conform to the public interface shown below: // Pre: none // Post: the BST is unchanged // Returns: true iff the BST is full // public boolean hasSingleChild( ) { // up to you. . . } Answer: // Pre: none // Post: the BST is unchanged // Returns: true iff the BST is full // public boolean hasSingleChild( ) { return hasSingleChild( root ); } private boolean hasSingleChild( BinaryNode sroot ) { // No node, so it can't have a single child. if ( sroot == null ) return false; // If current node has one non-null pointer, we are done. if ( ( sroot.left == null && sroot.right != null ) || ( sroot.left != null && sroot.right == null ) ) return true; // Otherwise, check the subtrees; due to the OR, we will stop our // search if one is found in the left subtree, without going into // the right subtree. return ( hasSingleChild( sroot.left ) || hasSingleChild( sroot.right) ); } 2. [20 points] This is a modification of question 1. Design an algorithm to count the number of single-child nodes in a binary search tree; that is, nodes that have exactly one child. Express your solution using Java code as if it were to be implemented as a public member function (with private helper) belonging to the BST generic specified in Minor Project 2; your answer (which will include both the public and private functions) must conform to the public interface shown below: // Pre: none // Post: the BST is unchanged // Returns: the number of nodes in the tree that have a single child // public boolean numSingleChildNodes( ) { // up to you. . . } Answer: // Pre: none // Post: the BST is unchanged // Returns: the number of nodes in the tree that have a single child // public int numSingleChildNodes( ) { return numSingleChildNodes( root ); } private int numSingleChildNodes( BinaryNode sroot ) { // No node, nothing to count here. if ( sroot == null ) return 0; // Setting up a counter for single-child nodes here and below. int thisOne = 0; // If this one has a single child, count it. if ( ( sroot.left == null && sroot.right != null ) || ( sroot.left != null && sroot.right == null ) ) thisOne = 1; // Get the counts from both subtrees, add in the count from // this node, and return the count. return ( thisOne + numSingleChildNodes( sroot.left ) + numSingleChildNodes( sroot.right ) ); } 3. [20 points] We say that two binary trees are congruent if and only if the two trees have exactly the same structure (arrangement of their nodes), without regard for the data values stored in the trees. Design an algorithm to determine whether two BSTs are congruent. Express your solution using Java code as if it were to be implemented as a public member function (with private helper) of some class belonging to same package as the BST implementation; your answer (which will include both the public and private functions) must conform to the public interface shown below: // Pre: none // Post: the BST is unchanged // Returns: the number of nodes in the tree that have a single child // public boolean areCongruent( BST A, BST B) { // up to you. . . } Answer: // Pre: none // Post: the BST is unchanged // Returns: the number of nodes in the tree that have a single child // public boolean areCongruent( BST A, BST B) { return areCongruent( A.root, B.root ); } private boolean areCongruent( BinaryNode leftroot, BinaryNode rightroot) { // If neither tree has a node here, they match. if ( leftroot == null && rightroot == null ) return true; // Since we already know that at least one tree has a node here, // if either of them does not, they they do not match. if ( leftroot == null || rightroot == null ) return false; // Otherwise, check the subtrees and AND the results. return ( areCongruent( leftroot.left, rightroot.left) && areCongruent( leftroot.right, rightroot.right) ); } 4. Assume that an implementation of the BST generic includes three functions as described below: // Writes the data elements in the tree (using their toString() method) // to the given output stream, using a preorder traversal. // // Pre: out is opened on a file // Post: the BST is unchanged // public void writePreorder( FileWriter out ) { . . . } // Writes the data elements in the tree (using their toString() method) // to the given output stream, using a postorder traversal. // // Pre: out is opened on a file // Post: the BST is unchanged // public void writePostorder( FileWriter out ) { . . . } // Writes the data elements in the tree (using their toString() method) // to the given output stream, using an inorder traversal. // // Pre: out is opened on a file // Post: the BST is unchanged // public void writeInorder( FileWriter out ) { . . . } a) [10 points] If writePreorder() and writeInorder() yield exactly the same output for a given nonempty BST, what must be true about that BST? Explain. Answer: At any given node X, we have two subtrees, Xleft and Xright (possibly empty). The preorder traversal will write: X -- nodes in Xleft -- nodes in Xright The inorder traversal will write: nodes in Xleft -- X -- nodes in Xright Those two output sequences will be identical iff there are no values in Xleft (note that those would all be smaller than X, so flipping X and any nodes in Xleft MUST produce different output). Therefore, the two traversals will produce the same output iff no node has a nonempty left subtree. b) [10 points] If writePreorder() and writePostorder() yield exactly the same output for a given nonempty BST, what must be true about that BST? Explain. Answer: At any given node X, we have two subtrees, Xleft and Xright (possibly empty). The preorder traversal will write: X -- nodes in Xleft -- nodes in Xright The postorder traversal will write: nodes in Xleft -- nodes in Xright -- X Those two output sequences MUST be different if there are any nodes in Xleft, for the reason given in part a. And, these two output sequences MUST be different if there are any values in Xright that are different from X. Therefore, the two traversals will produce the same output iff the tree is a "stalk" containing only copies of a single value (which would include an empty tree, and a tree with only a root node). 5. [20 points] Use Induction to prove the following theorem about binary trees: For every nonempty binary tree, the number of nodes that have two children is one less than the number of leaf nodes. Note: this is similar to the first part of the Full Binary Tree theorem, but different, since this does not assume anything special about the binary tree except that it is nonempty. Proof: For the same of clarity, let's define some notation. If T is a binary tree, we define leaves(T) = number of leaves in T twos(T) = number of nodes in T with two children We will use induction on the number of nodes N in the tree. If N = 1, the tree consists of a single node, which is a leaf. So, the number of leaves is 1 and the number of nodes with two children is 0, which satisfies the theorem. Now, suppose that for some N >= 1, if 0 <= K <= N then every binary tree with K nodes has one fewer nodes with two children than leaves. Suppose that T is a tree with N + 1 nodes. Now, T has a root node with two subtrees, say L and R (either of which could be empty). Since L has N or fewer nodes, the assumption above guarantees that the number of leaves in L, is one more than the number of nodes with two children in L; that is, twos(L) = leaves(L) - 1. By the same argument, twos(R) is one less than leaves(R). Note that all the leaves in T must be leaves in L or R, since the root cannot be a leaf if T has N + 1 nodes. Therefore leaves(T) = leaves(L) + leaves(R). Now, there are two cases: the root of T has two children, or not. If the root of T has two children, then twos(T) = twos(L) + twos(R) + 1 = (leaves(L) - 1) + (leaves(R) - 1) + 1 = leaves(L) + leaves(R) - 1 = leaves(T) - 1 If the root in T has fewer than two children, then one subtree is empty; without loss of generality, assume L is empty. Then twos(T) = twos(R) = leaves(R) - 1 = leaves(T) - 1 Therefore, the number of nodes in T that have two children is one less than the number of leaves in T. QED