How to return most frequent element in BinaryTree in Java

user_12367922 0
Viewed 213

I want to return number of values that is the most frequently in BinaryTree. I have BinaryClass which contain a lot of methods as add, contain, isEmpty, counter, iterator and other.I tried to implement this method public int getMaxFrequency() but I get a problem StackOverFlowException at markerd row.

When I run my code I get StackOverFlow Exception, anyone can help me please,

I'm new in BinaryTree.

Help me please.

enter code here
public class TreeSetCounter<T extends Comparable<T>> implements    Iterable<T>{
public Node<T> root; 
int size;
int count=0;

public TreeSetCounter() {
    root = null;
    size = 0;
   }
 public int counter(T t) {
 return counterRecursive(root, t);
  }

   public int counterRecursive(Node<T> root, T t) {
   int count = 0;
   if(root == null) {
        return 0;
          }
    if(root.value.equals(t)) {
      count++; 
      }
   count = count + counterRecursive(root.left, t)+           counterRecursive(root.right, t);
   return count; }


 public int getMaxFrequency(){
 
  return inorder(root);           
  }

  public int inorder( Node<T> prev) {
 
    int count = 1, max = 0;
    if (root == null) {
        return 0;}
    List<T> list = new ArrayList<>();
    inorder(root.left);   // I get the Exception att this row code.
    while (prev != null) {
    if (root.value == prev.value)
            count++;
        else
            count = 1;
    }
    
    if (count > max) {
        max = count;
        list.clear();
        list.add(root.value);
    } else if (count == max) {
        list.add(root.value);
    }
    prev = root;
    inorder(root.right);
    return max;
}

enter code here
Node.java
public class Node <T>{
T value;
int counter;
Node<T> left;
Node<T> right;

Node(T value, int count) {
    this.value = value;
    right = null;
    left = null;
    this.counter= count;
    }

enter code here
public static void main(String[] args) {
    TreeSetCounter <String> tsc= new TreeSetCounter<String>();
    tsc.add("java");
    tsc.add("java");
    tsc.add("not");
    tsc.add("cool");
    tsc.add("java");
    tsc.add("is");
    tsc.add("java");
    tsc.add("good");
    System.out.println(tsc.getMaxFrequency());}
stack-overflow binary-tree max exception java
1 Answers

Try something like this for your counter functions:

public int counter (T t) {
  if (root == null) return 0;
  
  int count = 0;
  if (root.value.equals(t))
    count++;
  
  count += counterRecursive(root.left, t);
  count += counterRecursive(root.right, t);

  return count;
}

public int counterRecursive (Node<T> root, T t) {
   if (root == null) return 0;
   
   if (root.value.equals(t))
    return 1 + counterRecursive(root.left, t) + counterRecursive(root.right, t);
   else
    return counterRecursive(root.left, t) + counterRecursive(root.right, t);
}

The counter function looks like the main method to use, and counterRecursive is your helper function. More complex recursive solutions typically have this kind of design pattern.

Think in terms of Fibonacci:

public static int fibonacci (int n) {
  return (n <= 1) ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

This should help you debug inOrder and getMaxFrequency. I would use counter in getMaxFrequency while I look through the rest. Generally speaking, using a HashMap or HashTable is much more adequate for keeping track of counts.

Try something like this:

public int getMaxFrequency () {
    if (root == null) return 0;
        
    HashMap<T, Integer> counts = new HashMap<T, Integer>();
        
    int count = counter(root.value);
    counts.put(root.value, count);

    // traverse the tree and grab counts
    int left = getMaxFrequencyHelper(root.left, counts, count);
    int right = getMaxFrequencyHelper(root.right, counts, count);

    return left > right ? left : right;
}

private int getMaxFrequencyHelper (Node<T> node, HashMap<T, Integer> counts, max) {
    if (node == null) return max;

    if (!counts.containsKey(node.value))
        counts.put(node.value, counter(node.value));

    int _max = counts.get(node.value) > max ? counts.get(node.value) : max;

    int left = getMaxFrequencyHelper(node.left, counts, _max);
    int right = getMaxFrequencyHelper(node.right, counts, _max);

    return left > right ? left : right;
}

This technique is called memoization where the previous counts are cached in a HashMap.

user_55568280
Related