Please complete the following based on the given partial program. Consider the f

Question

Please complete the following based on the given partial program.

Consider the following declaration of Class BinarySearchTree and TreeNode (an inner class):

public class BinarySearchTree
{
private static class TreeNode
{
// 3 private instance variables
  
private int data;
private TreeNode leftLink;
private TreeNode rightLink;
// One no-argument constructor for an empty node.
Public TreeNode()
{
data = 0;
leftLink = rightLink = null;
}
// One one-argument constructor
public TreeNode (int newData, TreeNode newLeftLink, TreeNode newRightLink)
{
data = newData;
leftLink = newLeftLink;
rightLink = newRightLink;
}
} //End of TreeNode inner class
  
// Declaration of class BinarySearchTree begins here.
  
// Three instance variables.
  
private TreeNode root;
private TreeNode parent;
private int parentLink;
  
// One no-argument constructor for creating an empty binary tree.
  
public BinarySearchTree ( )
{
root = parent = null;  
parentLink = 0;
}

// One copy constructor to create one by making a deep copy of an existing BST given
// by the root of the tree which is the lone parameter.
public BinarySearchTree (TreeNode rootNode)
{
    parent = null;
    parentLink = 0;
   root = copyBST (rootNode);
}

public TreeNode copyBST (TreeNode rootNode)
// Recursively copies a BST rooted at the given rootNode and returns
// the root node of the copied BST.
{
   if (rootNode == null) return rootNode;
   //    else the current tree or subtree not empty yet.
   TreeNode leftChild = copyBST (rootNode.leftLink);
   TreeNode rightChild = copyBST (rootNode.rightLink);
   return new TreeNode (rootNode.data, leftChild, rightChild);
}

public BinarySearchIree copyRight CTreeNode givenNode) This method will (1) make a deep copy of the right subtree of the current (calling) binary search tree after replacing the current root of the right subtree with the givenNode and (2 retum the resulting somewhat modified right subtree.

Explanation / Answer

public class BinarySearchTree
{
private static class TreeNode
{
// 3 private instance variables
  
private int data;
private TreeNode leftLink;
private TreeNode rightLink;
// One no-argument constructor for an empty node.
Public TreeNode()
{
data = 0;
leftLink = rightLink = null;
}
// One one-argument constructor
public TreeNode (int newData, TreeNode newLeftLink, TreeNode newRightLink)
{
data = newData;
leftLink = newLeftLink;
rightLink = newRightLink;
}
} //End of TreeNode inner class
  
// Declaration of class BinarySearchTree begins here.
  
// Three instance variables.
  
private TreeNode root;
private TreeNode parent;
private int parentLink;
  
// One no-argument constructor for creating an empty binary tree.
  
public BinarySearchTree ( )
{
root = parent = null;  
parentLink = 0;
}

// One copy constructor to create one by making a deep copy of an existing BST given
// by the root of the tree which is the lone parameter.
public BinarySearchTree (TreeNode rootNode)
{
    parent = null;
    parentLink = 0;
   root = copyBST (rootNode);
}

public TreeNode copyBST (TreeNode rootNode)
// Recursively copies a BST rooted at the given rootNode and returns
// the root node of the copied BST.
{
   if (rootNode == null) return rootNode;
   //    else the current tree or subtree not empty yet.
   TreeNode leftChild = copyBST (rootNode.leftLink);
   TreeNode rightChild = copyBST (rootNode.rightLink);
   return new TreeNode (rootNode.data, leftChild, rightChild);
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.