Please complete the following problem using java language. Consider the followin

Question

Please complete the following problem using java language.

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 TreeNode predecessor TreeNode theParent, int linknumber) This method will find and return the immediately preceding node of a given node in terms integer values ofthe tree nodes. Note that the node is given by the two parameters of this method such that the first one is its parent node and the second indicates whether the node is the left child (when linknumber 1) or the right child (when it linknumber 2) of its parent node. And, when the node does not have a parent (as is the case when it is the tree root itself its parent is given as null. of course, when there is no such predecessor node (which is the case when the given node is the smallest node of the entire current tree). then null will be returned.

Explanation / Answer

public TreeNode predecessor(TreeNode theParent, int linknumber)
{
   TreeNode rootNode = root;
   //in case where the root matches the target node
   if(rootNode.data == theParent.data)
       return null;

   while(rootNode != null)
   {
       //linknumber 1 means left child
       if(linknumber == 1 && rootNode.leftLink != null)
       {
           if(rootNode.leftLink.data == theParent.data)
               return rootNode;
           else rootNode = rootNode.leftLink;
       }
       //link number 2 means right child
       else if(linknumber == 2 && rootNode.rightLink)
       {
           if(rootNode.rightLink.data == theParent.data)
               return rootNode;
           else rootNode = rootNode.rightLink;
       }
   }
   return null;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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