Question

In Java

Write a method countOddInternalNodes that returns the number of internal nodes in a binary tree that contain odd numbers.

You are essentially writing a method that will become part of the IntegerTree class.

You may define private helper methods to solve this problem.

Make your own trees in the main method of the code. I specifically kept vague the way the nodes are being added to the tree so you can practice building your own trees from scratch and testing your code on them.

Example

If a variable tree stores a reference to the following tree:

          +---+
          | 2 |
          +---+
         /     \
     +---+     +---+
     | 8 |     | 1 |
     +---+     +---+
    /         /     \
+---+     +---+     +---+
| 3 |     | 7 |     | 6 |
+---+     +---+     +---+
         /               \
     +---+               +---+
     | 4 |               | 9 |
     +---+               +---+

Then the call tree.countOddInternalNodes(); should return 2 because there are two branch nodes with even values (1 and 7).

Notice that the leaf nodes with odd values are not included (the nodes storing 3 and 9).

Resources

Watch this video on how to solve a similar problem.

Testing

As part of the exercise, you should construct the main function to test your code.

Add the nodes to the tree manually in the main method.

In doing so, you can test examples like the tree given in the example above.

A default array like the one below is given for you to test your tree on, but you have no way of knowing how the elements in that array are going to be inserting in the tree. Therefore, you should make your own trees and test your code on them.

Integer Tree class(No change needed)

// This class represents a tree of integers
public class IntegerTree {
private IntegerTreeNode root;

// Constructs a tree
public IntegerTree() {
root = null;
}
// Getters
public IntegerTreeNode getRoot() {
   return root;
}
// Setters
public void setRoot(IntegerTreeNode node) {
   root = node;
}
}

Integer Tree Node class(No change needed)

// Class that represents a single node in the tree
public class IntegerTreeNode {
public int data; // data stored at this node
public IntegerTreeNode left; // reference to left subtree
public IntegerTreeNode right; // reference to right subtree

// Constructs a leaf node with the given data.
public IntegerTreeNode(int data) {
this(data, null, null);
}

// Constructs a leaf or branch node with the given data and links.
public IntegerTreeNode(int data, IntegerTreeNode left, IntegerTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}

Main class

import java.util.*;

public class Main {
public static void main (String [] args) {
//Variables
int [] defaultArr = {33,45,2,21,46,3,1,32,11,211,10};
  
/*
* Enter code here to build your own trees manually and test the countOddInternalNodes() method on them
*/

}
}

OddNodeCounter class

public class OddNodeCounter extends IntegerTree {
public OddNodeCounter(){
super();
}
public int countOddInternalNodes(IntegerTreeNode root){
//Enter code here

}
}

Answer 1

HI,

Please find updated code below.

Main.java:

import java.util.*;

public class Main
{
public static void main (String [] args)
{
//Variables
int [] defaultArr = {33,45,2,21,46,3,1,32,11,211,10};
IntegerTree myTree = new IntegerTree();
OddNodeCounter oddCOunter = new OddNodeCounter();
/*
* Enter code here to build your own trees manually and test the countOddInternalNodes() method on them
*/
//IntegerTreeNode myTree = myTree.getRoot();
IntegerTreeNode root = myTree.getRoot();
root = myTree.insert(root, defaultArr[0]);
myTree.setRoot(root);
  
for(int i =1;i<defaultArr.length;i++)
{
root = myTree.insert(myTree.getRoot(), defaultArr[i]);
}
myTree.inOrder(myTree.getRoot());
myTree.printinTreeFormat(myTree.getRoot());
int noOfOddInternalNodes = oddCOunter.countOddInternalNodes(root);
System.out.print("No of odd internal nodes are : " + noOfOddInternalNodes);
}
}

IntegerTree.java:

public class IntegerTree
{
private IntegerTreeNode root;
  
// Constructs a tree
public IntegerTree()
{
root = null;
}
// Getters
public IntegerTreeNode getRoot()
{
return root;
}
// Setters
public void setRoot(IntegerTreeNode node)
{
root = node;
}
static IntegerTreeNode newNode(int item)
{
IntegerTreeNode temp = new IntegerTreeNode(item);
temp.data = item;
temp.left = null;
temp.right = null;
return temp;
}
static IntegerTreeNode insert(IntegerTreeNode node, int key)
{
/* If the tree is empty, return a new node */
if (node == null)
{
System.out.println("first time");
return newNode(key);
}
  
/* Otherwise, recur down the tree */
if (key < node.data)
node.left = insert(node.left, key);
else
node.right = insert(node.right, key);
  
/* return the (unchanged) node pointer */
return node;
}
static void printinTreeFormatUtil(IntegerTreeNode root, int mySpace)
{
int COUNT = 11;
// Base case
if (root == null)
return;
  
mySpace += COUNT;
printinTreeFormatUtil(root.right, mySpace);
  
  
System.out.print("\n");
for (int i = COUNT; i < mySpace; i++)
System.out.print(" ");
System.out.print(root.data + "\n");
  
printinTreeFormatUtil(root.left, mySpace);
}
  
// Wrapper over printinTreeFormatUtil()
static void printinTreeFormat(IntegerTreeNode root)
{
// Pass initial space count as 0
printinTreeFormatUtil(root, 0);
}
  
public void inOrder(IntegerTreeNode root)
{
if (root != null)
{
//System.out.print("Im here");
inOrder(root.left);
System.out.print(root.data + " ");
inOrder(root.right);
}
}
}

IntegerTreeNode.java

public class IntegerTreeNode
{
public int data; // data stored at this node
public IntegerTreeNode left; // reference to left subtree
public IntegerTreeNode right; // reference to right subtree
  
// Constructs a leaf node with the given data.
public IntegerTreeNode(int data)
{
this(data, null, null);
}
  
// Constructs a leaf or branch node with the given data and links.
public IntegerTreeNode(int data, IntegerTreeNode left, IntegerTreeNode right)
{
this.data = data;
this.left = left;
this.right = right;
}
}

OddNodeCOunter.java

public class OddNodeCounter extends IntegerTree
{
int count =0;
public OddNodeCounter()
{
super();
}
boolean isLeaf(IntegerTreeNode node)
{
if (node == null)
return false;
if (node.right == null && node.left == null)
return true;
return false;
}
public int countOddInternalNodes(IntegerTreeNode root)
{
if (root != null)
{
countOddInternalNodes(root.left);
  
// if node is odd then print it
if (root.data % 2 != 0 && !isLeaf(root))
{
count++;
//System.out.println("Odd:" + root.data + " ");
}
countOddInternalNodes(root.right);
}
  
return count;
}
  
}

Output tree and output from program attached:

program output:

Thanks,

kindly upvote.