Modify the below code to implement a variable called \'parent\' which is the par

Question

Modify the below code to implement a variable called 'parent' which is the parent of a node. Modify the 'insert' method to adjust the class. Add a test class and that constructs the tree with values: 14, 11, 17, 4, 53, 9, 7, 19, 13. Find the parent of node 53 and 13.

public class BinarySearchTree {
   private static final String root = null;
   public boolean search1(int value) { // in this case value is equal to k in the lab assignment
       if (root==null){
           return false;
       }
       else{
           return root.search(value);
       }  
   }
  
   public boolean search(int value) {
if (value==this.value)
return true;
else if (value< this.value) {
if (left==null)
return false;
else
return left.search(value);
} else if (value>this.value) {
if (right==null)
return false;
else
return right.search(value);
}
return false;
}
   public boolean insert(int value){
       if (root==null){
           root=new BSTNode(value);
           return true;
       }
       else {
           return root.insert(value);
       }
   }
  
   public class BSTNode {
       public boolean insert(int value){
           if (value==this.value){
               return false;
           }
           else if (value<this.value){
               if(left==null){
                   left=BSTNode(value);
                   return true;
               }
           }
           else{
               return right.insert(value);
               }
           return false;
       }
   }

Explanation / Answer

The code was incomplete and had too many errors. Below is complete and working code of BST with parent info added to each node

class BSTNode
{
int value;
BSTNode left, right, parent;
  
public BSTNode(int n)
{
left = null;
right = null;
parent=null;
value = n;
}
}
public class BinarySearchTree {
private BSTNode root = null;
public BinarySearchTree()
{
root = null;
}
public boolean search(int val)
{
return search(root, val);
}
private boolean search(BSTNode r, int val)
{
boolean found = false;
while ((r != null) && !found)
{
int rval = r.value;
if (val < rval)
r = r.left;
else if (val > rval)
r = r.right;
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
public BSTNode insert(BSTNode node, BSTNode parent, int value){
if (node == null)
{
node = new BSTNode(value);
node.parent=parent;
}
else
{
if (value <= node.value)
node.left = insert(node.left, node, value);
else
node.right = insert(node.right, node, value);
}
return node ;
}

public void display(BSTNode node)
{
if (node == null)
return;

/* first recur on left child */
display(node.left);

/* then print the data of node */
System.out.print(node.value + " ");

/* now recur on right child */
display(node.right);   
}
public void displayParent(BSTNode node, int value)
{
if (node == null)
return;

  
displayParent(node.left, value);

  
if(node.value==value) System.out.println(" Parent of "+node.value+" is "+node.parent.value + " ");

  
displayParent(node.right, value);
}




///////////Main

public static void main(String a[])
{
BinarySearchTree b = new BinarySearchTree();
BSTNode root=new BSTNode(14);
b.root=root;

b.insert(root,null, 11);
b.insert(root,null, 17);
b.insert(root,null, 4);
b.insert(root,null, 53);
b.insert(root,null, 9);
b.insert(root,null, 7);
b.insert(root,null, 19);
b.insert(root,null, 13);

b.display(root);
b.displayParent(root,53);
b.displayParent(root,13);
}
}
  

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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