sampleInput: 2 1 public class BinaryTree { private Node root; /** Constructs an

Question

sampleInput: 2 1

public class BinaryTree
{
private Node root;

/**
Constructs an empty tree.
*/
public BinaryTree() { root = null; }

/**
Constructs a tree with one node and no children.
@param rootData the data for the root
*/
public BinaryTree(Object rootData)
{
root = new Node();
root.data = rootData;
root.left = null;
root.right = null;
}

/**
Constructs a binary tree.
@param rootData the data for the root
@param left the left subtree
@param right the right subtree
*/
public BinaryTree(Object rootData, BinaryTree left, BinaryTree right)
{
root = new Node();
root.data = rootData;
root.left = null;
root.right = null;
if (left != null) { root.left = left.root; }
if (right != null) { root.right = right.root; }
}

class Node
{
public Object data;
public Node left;
public Node right;
}

/**
Returns the height of the subtree whose root is the given node.
@param n a node or null
@return the height of the subtree, or 0 if n is null
*/
private static int height(Node n)
{
if (n == null) { return 0; }
else { return 1 + Math.max(height(n.left), height(n.right)); }
}

/**
Returns the height of this tree.
@return the height
*/
public int height() { return height(root); }

/**
Checks whether this tree is empty.
@return true if this tree is empty
*/
public boolean isEmpty() { return root == null; }

/**
Gets the data at the root of this tree.
@return the root data
*/
public Object data() { return root.data; }

/**
Gets the left subtree of this tree.
@return the left child of the root
*/
public BinaryTree left()
{
BinaryTree result = new BinaryTree();
result.root = root.left;
return result;
}

/**
Gets the right subtree of this tree.
@return the right child of the root
*/
public BinaryTree right()
{
BinaryTree result = new BinaryTree();
result.root = root.right;
return result;
}
}

=================================================================

import java.util.*;

public class PoD
{

//=============================================================================
/**
* Returns true if the binary tree is a strict binary tree, in which
* each node in the tree has either zero or two children.
* @param bTree BinaryTree of interest
* @return boolean true if strict binary tree, false otherwise
*/

public static boolean isStrictBinaryTree(BinaryTree bTree)
{

}

//=============================================================================

public static void main( String [] args )
{

Scanner in = new Scanner( System.in );

int i = in.nextInt();
int j = in.nextInt();

BinaryTree newBT = makeBT(i,j);

boolean isStrictBT = isStrictBinaryTree(newBT);

if (isStrictBT) {
System.out.println("Strict binary tree");
}
else {
System.out.println("NOT a strict binary tree");
}

in.close();

System.out.print("END OF OUTPUT");
}

public static BinaryTree makeBT(int n, int k)
{
BinaryTree b;
if ((n>0) && (n%2==0))
{
b = new BinaryTree(n,makeBT(n-1,k),makeBT(n-2,k));
}
else if (n>0 & n%2==k) {
b = new BinaryTree(n, null, makeBT(n - 2,k));
}
else
{
b = new BinaryTree(0,null,null);
}

return b;

}
}

Explanation / Answer

/* providing the both function one private and one public
       * the basic algorithm is to check the left and right side if both are null then
       * return true, if any one of them exist and other does not return false
       * if both exist then check the left subtree and right sub tree
       */
       public boolean isStrictBinaryTree() {
           return isStrictBinaryTree(root);
       }
       private boolean isStrictBinaryTree(Node parent) {
           // if right child exist but left does not
           if (parent.left == null && parent.right != null) {
               return false;
           }
           // if left exist but right does not
           if (parent.right == null && parent.left != null) {
               return false;
           }
           // if both does not exist then 0 children
           if (parent.left == null && parent.right == null) {
               return true;
           }
           // if both exist then check subtrees
           boolean>            boolean two = isStrictBinaryTree(parent.right);
           if (!one || !two) {
               return false;
           }
           return true;

       }

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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