Question

Create a recursive method that takes as input the root Node of a tree and returns true if the N variable of each node within that tree has the correct value (i.e., all nodes are labeled with the proper size of the subtree they define), and false otherwise.

Answer 1

Program :

import java.util.Scanner;
class BTNode{  
     BTNode left, right;
     int data;
     public BTNode(){
         left = null;
         right = null;
         data = 0;
     }
     public BTNode(int n){
         left = null;
         right = null;
         data = n;
     }
     public void setLeft(BTNode n){
         left = n;
     }
     public void setRight(BTNode n){
         right = n;
     }
     public BTNode getLeft(){
         return left;
     }
     public BTNode getRight(){
         return right;
     }
     public void setData(int d){
         data = d;
     }
     public int getData()

     {

         return data;

     }   

}
class BT{
     private BTNode root;
     public BT(){
         root = null;
     }
     public boolean isEmpty(){
         return root == null;
     }
     public void insert(int data){
         root = insert(root, data);
     }
     private BTNode insert(BTNode node, int data){
         if (node == null)
             node = new BTNode(data);
         else{
             if (node.getRight() == null)
                 node.right = insert(node.right, data);
             else
                 node.left = insert(node.left, data);           
         }
         return node;
   }  
   public void inorder(){
         inorder(root);
     }
     private void inorder(BTNode r){
         if (r != null){
             inorder(r.getLeft());
             System.out.print(r.getData() +" ");
             inorder(r.getRight());
         }
     }
   public boolean search(int val){
         return search(root, val);
     }
   private boolean search(BTNode r, int val){
         if (r.getData() == val)
             return true;
         if (r.getLeft() != null)
             if (search(r.getLeft(), val))
                 return true;
         if (r.getRight() != null)
             if (search(r.getRight(), val))
                 return true;
         return false;       

     }
}

public class BinaryTree{
   public static void main(String[] args){
       Scanner scan = new Scanner(System.in);
        BT bt = new BT();
        char ch;
       System.out.println("#############Binary Tree ###################");
        do{
            System.out.println("Enter integer element to insert :");
            bt.insert(scan.nextInt());
            System.out.print(" In order : ");
            bt.inorder();
           System.out.print(" ");
           System.out.println(" Do you want to continue (Type y or n) : ");
           ch = scan.next().charAt(0);
        } while (ch == 'Y'|| ch == 'y');
       System.out.println("Enter a node value to check is correct or not in the tree :");
       int a = scan.nextInt();
       System.out.println(bt.search(a));
    }
}

import java.util.Scanner class BTNode f ...BTNode left, right int data; public BTNode ) left = null ; right-=-null ; ..public BTNode (int-n) f left- null; right-=-null ; ..public void setLeft (BTNode n) i left .= n; ..public void setRight (BTNode -n) i ..public BTNode getLeft) return left; ..public BTNode getRight) return right: ..public void setData (int .d) -data-=-d ..public int.getData ()

class BT ..private BTNode root: ..public BT ) ..public boolean isEmpty)i ..public void insert (int data) ..private BTNode insert (BTNode node, int data) if (node.getRight ()ull) ..node.right-insert (node.right, data) -ellse ー> .public .void inorder ( ) { inorder (root) ..private void inorder (BTNode r) inorder (r.getLeft) System.out.print (r.getData) +"") inorder (r.getRight )

public.boolean search (int val) f return search (root, val) 一»-private-boolean . search (BTNoder, .int .val)( if (r.getData() return true val) return true .return true return false; public class BinaryTree 一»-public. static .void main (String[] args) { .Scanner scan- new Scanner (System.in); char ch System.out.print("nIn order : ") System.out.print ("n") ーー>- . System. out . printin ("\n\nDo . you-want . to . continue . (Type-y-or-n) . : -") ; chscan.next () .charAt (O) while (ch _Y11 ch- y') System. out . printin ("Enter .a-node-value . to . check is . correct-or-not in . the . tree . : ") ; ー--> int a-, s can . next Int ( ) ; System.out.println (bt.search (a))

Output :

Command Prom Enter integer element to insert: 10 In order 1 Do you want to continue (Type y or n) Enter integer element to insert: In order10 1 Do you want to continue (Type y or n) Enter integer element to insert: In order 10 1 Do you want to continue (Type y or n) Enter integer element to insert: In order:0 11 10 1 Do you want to continue (Type y or n) Enter integer element to insert: In order4 0 11 10 1 Do you want to continue (Type y or n) Enter a node value to check is correct or not in the tree: true