CODEWITHSUNDEEP
pythonbinary-search-tree
Cero
Cero

Reputation: 205

Counting words using a Binary Tree in Python?

I am not sure how to implement a counter within a binary tree class. As I would like to be able to keep track of the frequency of a word. My issue is that I don't know where to start counting within the insert function.

class _Node:
def __init__(self, value, left=None, right=None):
    self._value = value
    self._left = left
    self._right = right
    self._count = 0

class BinaryTree:

def __init__(self):
    self._root = None

def isEmpty(self):
    return self._root == None

def insert(self, value) :
    if self.isEmpty() :
        self._root = _Node(value)
        return
    parent = None
    probe = self._root
    while (probe != None) :
        if value <= probe._value :
            parent = probe
            probe = probe._left

        else :
            parent = probe
            probe = probe._right            

    if (value <= parent._value) :
        parent._left = _Node(value)
    else :
        parent._right = _Node(value)

Upvotes: 0

Views: 1469

Answers (1)

Blckknght
Blckknght

Reputation: 104712

I suspect you want an extra condition on the if/else you're checking inside the while loop in insert that handles the situation where the value you're inserting is equal to probe._value. Something like:

if value == probe._value:
    probe._count += 1
    return
elif value < probe._value:
    # the rest as before

You also probably want your _Node class to initialize _count to 1 rather than 0.

Upvotes: 1

Related Questions