This question is in two parts Part 1: You will implement 3 recursive methods tha

Question

This question is in two parts

Part 1:

You will implement 3 recursive methods that operate on binary trees (any binary trees, not necessarily balanced, not necessarily BSTs). All methods take a reference to the root node.

a)     Implement a method that finds the number of nodes in the longest path in the given tree.

static int longestPath(Node root) {

You will implement 3 recursive methods that operate on binary trees (any binary trees, not necessarily balanced, not necessarily BSTs). All methods take a reference to the root node.Implement a method that finds the number of nodes in the longest path in the given tree.static int longestPath(Node root) { ... } As an example, for a full tree with 3 nodes this would return 2, but for a degenerate tree with 3 nodes looking like a linked list it would return 3. Implement a method that sets the data member of all the nodes in the tree to the size of the subtree rooted at that node. static void setSize(Node root) { ... } As an example, for a full tree with 3 nodes this would set the data member of the root node to 3 and the data member of each child to 1. Implement a method that changes the tree as if it was flipped left to right. static void flip(Node root) { ... } You will implement a method that reads in the given students file and counts how many times each first name occurs. It then prints in alphabetical order only the first names that occur "threshold" or more times and their occurrence count, one name-count per line. static void printFrequentNames(String filename, int threshold) { ... }

Explanation / Answer

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Iterator;

import java.util.Map;

import java.util.Scanner;

import java.util.Set;

import java.util.TreeMap;

public class TreeCode {

static class Node {

Node(int data) {

this.data = data;

}

int data;

Node left;

Node right;

}

/*

* Part 1 - a This method will get the largest path

*/

static int longestPath(Node root) {

if (root == null) {

return 0;

} else {

// compute the depth of each subtree

int left = longestPath(root.left);

int right = longestPath(root.right);

// use the larger one

if (left > right)

return (left + 1);

else

return (right + 1);

}

}

/*

* Part 1 - b

*/

static void setSize(Node root) {

//Checking if the root is null

if (root != null) {

// if not, increment the counter by 1

root.data = 1;

if(root.left != null){

// if there exist a left child, increment the counter by 1

root.data += 1;

setSize( root.left);

}

if(root.right != null){

// if there exist a right child, increment the counter by 1

root.data += 1 ;

setSize(root.right);

}

}

}

/*

* Part 1 - c

*/

static void flip(Node root) {

//changing the left and right using swap method.

Node temp = root.left;

root.left = root.right;

root.right = temp;

//keep doing this (by recursion) unless the last node i.e leaf is not found.

if(root.left != null) flip(root.left);

if(root.right != null) flip(root.right);

}

/*

* Part 2

*/

static void printFrequentNames(String filename, int threshold) {

try {

//Creating an instance of Scanner

Scanner scanner = new Scanner(new File(filename));

//Creating a tree map

TreeMap<String, Integer>treeMap = new TreeMap<String, Integer>();

//Reading values from the file, one line at a time.

while (scanner.hasNextLine()) {

String line = scanner.nextLine();

//Seperating the first name from the line

String[] lineSplit = line.split("\s");

  

int mapValue = 0;

//Checking if the tree map already contains the key i.e the first name

if(treeMap.containsKey(lineSplit[0])){

// if yes, then get the value of the tree map and increase it by 1 and make the entry again in the map

mapValue= treeMap.get(lineSplit[0]);

mapValue = mapValue+1;

treeMap.put(lineSplit[0],mapValue);

}

else

// if no match is found, then put the first name with counter =1

treeMap.put(lineSplit[0],1);

  

}

//Converting the map to set

Set set = treeMap.entrySet();

// Creating an instance of iterator

Iterator iterator = set.iterator();

// Display elements

while(iterator.hasNext()) {

Map.Entry me = (Map.Entry)iterator.next();

int value = (Integer) me.getValue();

//if the value is greater than or equal to //threshold value, then only print the map key value pair else //skip.

if (value>= threshold){

System.out.print(me.getKey() + " ");

System.out.println(me.getValue());

}

}

  

//handling exception

} catch (FileNotFoundException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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