Keeping track of word frequency using a binary tree

Question

I'm currently learning about binary trees and binary search trees, and one of the exercises I'm working on involves reading a text file, storing each word in a binary tree alphabetically, and traversing the tree using different methods. Here are the exact specifications:

Read in the text and build a binary search tree comprising of all the words in the text (based alphabetically), store the word and keep a count of the word's frequency (the number of times each word appears in the text) in a node, and perform tree traversals mentioned in class.

My question is, how can I keep track of a word's frequency when I'm adding it to the tree? We've never covered identical nodes in class, so I'm stuck here. Any suggestions are appreciated!

Answer 1

Simple. Binary tree node will comprise of two elements one being the string (say the key) and the other being the integer count (say the value). While adding an element check as to if it is already there, if yes then simply increment count else add the element as a new binary tree node with a count of 1.

Answer 2

Tricky answering homework questions...

So, your node would obviously hold the word it is representing. When you insert a new word you create the node, but before you do that, you SEARCH for the word. If a node for the word already exists in your tree, simply retrieve the node and increase a counter in it.

public class MyNode
{
   String word;
   Integer counter;
}

Get it? :)

Answer 3

how can I keep track of a word's frequency when I'm adding it to the tree

1) Besides the data left and right members of a TreeNode add another member count and increment by 1 each time you try to add an existing word in the tree.

2) You could use a separate hash table to keep a mapping of words and the occurences. If the word exists in the hash table just increment the count. If it does not exist add it to the tree. This requires extra space due to hash table

Answer 4

Use a HashMap, fill it with String, Integer. Iterate over the words in the text, put it in the map with Integer(occurrence) == 1 if it isn't added yet. If it was added before, augment the Integer with 1.

When all text is processed, you can for example fill a list with objects with a String and and Integer, sort them according to their compareTo method.

Answer 5

in case someone in need.

an implementation of scala BST container.

trait BSTree[+A]

case object Empty extends BSTree[Nothing]

case class Node[+A](left: BSTree[A], x: A, right: BSTree[A]) extends BSTree[A]

object BSTree {

  def insert[T](t: BSTree[T], k: T)(
    implicit ord: T => Ordered[T]
  ): BSTree[T] = t match {
    case Empty => Node(Empty, k, Empty)
    case Node(l, x, r) if k < x => Node(insert(l, k), x, r)
    case Node(l, x, r) if k == x => Node(l, k, r)
    case Node(l, x, r) => Node(l, x, insert(r, k))
  }

  def toList[T](t: BSTree[T]): List[T] = t match {
    case Empty => Nil
    // preorder traverse
    case Node(l, x, r) => x :: toList(l) ++ toList(r)
  }

  def apply[T](as: T*)(implicit ord: T => Ordered[T]): BSTree[T] = as.foldLeft(
    Empty: BSTree[T])((t, e) => insert(t, e))
}

object Main extends App {
    case class WordCount(c: Char, var count: Int) {
    override def toString: String = s"'$c' -> $count"
  }

  implicit def wordCountConvert(x: WordCount): Ordered[WordCount] =
    (that: WordCount) => if (x.c.<(that.c)) -1
    else if (x.c == that.c) {
      that.count = x.count + 1
      0
    } else 1

  val content = "Scala Cool!"
  val wordCountTree = BSTree(content.filter(_.isLetter).map(WordCount(_, 1)): _*)
  println(BSTree.toList(wordCountTree))
}

and output here

List('S' -> 1, 'C' -> 1, 'c' -> 1, 'a' -> 2, 'a' -> 1, 'l' -> 2, 'o' -> 2, 'l' -> 1, 'o' -> 1)

see example here