Fill This Form To Receive Instant Help

Help in Homework
trustpilot ratings
google ratings


Homework answers / question archive / 1)Design and implement a method leafCount for BinarySearchTree that returns the number of leaves in the tree 2) Design and implement a method oneChild for BinarySearchTree that returns the number of nodes in the tree that have exactly one child 3) Design and implement a method height for BinarySearchTree, that returns the height of the tree

1)Design and implement a method leafCount for BinarySearchTree that returns the number of leaves in the tree 2) Design and implement a method oneChild for BinarySearchTree that returns the number of nodes in the tree that have exactly one child 3) Design and implement a method height for BinarySearchTree, that returns the height of the tree

Computer Science

1)Design and implement a method leafCount for BinarySearchTree that returns the number of leaves in the tree

2) Design and implement a method oneChild for BinarySearchTree that returns the number of nodes in the tree that have exactly one child

3) Design and implement a method height for BinarySearchTree, that returns the height of the tree

pur-new-sol

Purchase A New Answer

Custom new solution created by our subject matter experts

GET A QUOTE

Answer Preview

Answer:

1. implementation of method leafcount:

class Node
{
    int data;
    Node left, right;

    public Node(int item)                  // creating a node
    {
        data = item;
        left = right = null;
    }
}

/* Class to find leafcount of Binary Tree */
class BinaryTree
{
    Node root;

    /* Given a binary tree. Print its nodes in level order
       using array for implementing queue */
    int leafCount()
    {
        return leafCount(root);
    }

    /* find number of leaf in tree */
    int leafCount(Node node)
    {
        if (node == null)
            return 0;
        else
            return(leafCount(node.left) + 1 + leafCount(node.right)); /* every node will return 1+ so at the end it will return total leafCount
                                                                      This is a recursive call. first it will count left subtree recursively
                                                                     then head nodes and then right subtree*/
    }


    public static void main(String args[])
    {
        /* creating a binary tree*/
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("The leafcount of binary tree is : "
                            + tree.leafCount());
    }
}

OUTPUT:

The leafcount of binary tree is : 5

Answer 2: method that print number of node having one child

class Node
{
   int key;
   Node left, right;
    public static int count;     // count variable to count number of node having single child
   public Node(int item)       // creating a node
   {
       key = item;
       left = right = null;
  
   }
}

class BinaryTree
{

   Node root;

   BinaryTree()
   {
       root = null;
   }

/*
    Method which count number of node having only one child
Logic:

traversing through the tree and if node has either left or right address only and rest one is null then it has only one child.
so counting all node and printing class variable "count"

*/
void oneChind(Node node)
   {
       if (node == null)
           return;
          
        if(((node.left == null) && (node.right!= null)) || ((node.right == null) && (node.left!= null))) // if only left or only right available then increment count
        {
            node.count++;
              System.out.print( "Incrementing count by 1\n");
        }
       //recur on left subtree
       oneChind(node.left);

       // then recur on right subtree
       oneChind(node.right);
  
   }

   // Wrappers function
   void oneChind() {   oneChind(root); }

   // Driver method
   public static void main(String[] args)
   {
       BinaryTree tree = new BinaryTree();
       tree.root = new Node(1);
       tree.root.right = new Node(2);
       tree.root.right.right = new Node(3);
       tree.root.right.left = new Node(4);
       tree.root.right.right.left = new Node(5);

/*
   creating tree like this:

              (1)
                 \
                  (2)
                /    \
             (4)    (3)
                    /
                 (5)
              

*/
       System.out.println("\n oneChild node count is");
       tree.oneChind();
           System.out.print(   tree.root.count + "\n ");
          
           // OUTPUT: oneChild node count is 2. ( node 2 and node 3)
   }
}

Answer 3: height function that return height of tree:

// Java program to find height of tree
class Node
{
    int data;
    Node left, right;

    Node(int i)     // creating anode
    {
        data = i;
        left = right = null;
    }
}

class BinaryTree
{
     Node root;

   /*
   height function will return height of the tree. but the thing is it should be maximum. so each every step from bottom we compare height of left and right.
   which one is greater it will retuen. at the end, root has max height from left and right. so it will return 1 + max_height
   */
   int height(Node node)
    {
        if (node == null)
            return 0;
        else
        {
            /* compute the depth of each subtree */
            int left_height = height(node.left);
            int right_height = height(node.right);

            /* use the larger one */
            if (left_height > right_height)   // if left is greater then return left +1
                return (left_height + 1);
             else
                return (right_height + 1);    // else return right +1
        }
    }

    
    /* program to test above functions */
    public static void main(String[] args)
    {
        BinaryTree Tree = new BinaryTree();

        Tree.root = new Node(1);
        Tree.root.left = new Node(2);
        Tree.root.right = new Node(3);
        Tree.root.left.left = new Node(4);
        Tree.root.left.right = new Node(5);

        System.out.println("Height of tree is" +
                                      Tree.height(Tree.root));
    }
}