Python: search in binary search tree

Question

I have a binary search tree with words from a file and now I'd like to search a word from it and it should return the length and how many times this word has occurred. I'm not sure how to start from the root and how to proceed from there. a little explanation with some examples would be much appreciated.

I have attached my current code:

class Node:
def __init__(self, value, left=None, right=None):
    self.left = left
    self.right = right
    self.value = value
    self.count = 1

def add(self, value):
    if self.value == value:
        self.count += 1
    elif value < self.value:
        if self.left is None:
            self.left = Node(value)
        else:
            self.left.add(value)
    else:
        if self.right is None:
            self.right = Node(value)
        else:
            self.right.add(value)

def printTree(self):
    if self.left is not None:
        self.left.printTree()
    print(str(self.value) + " " + str(self.count))
    if self.right is not None:
        self.right.printTree()





def processFileContent(file):
    words = []
    for line in file:
        unprocessedWords = re.split(" ", line)

    for word in unprocessedWords:
        word = word.lower()
        if word.isalpha():
            words.append(word)

return words


def processFile():
    file = open("text.txt", "r")
    words = processFileContent(file)
    file.close()
    return words


def createTree(words):
    if len(words) > 0:
        tree = Node(words[0])
        for word in words:
            tree.add(word)
        return tree
    else:
        return None

def main():
    words = processFile()
    tree = createTree(words)
    tree.printTree()

Scott Hunter · Accepted Answer · 2014-12-18 19:42:01Z

1

Note that adding to a BST involves searching for where the value should be and then putting it there; so if you can build one, you should be able to search one.

answered Dec 18, 2014 at 19:42

Scott Hunter

50k12 gold badges64 silver badges107 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

pirelius · Accepted Answer · 2014-12-18 22:30:02Z

0

I did it like this and seems to do the thing

def search(tree, word):
    node = tree
    depth = 0
    count = 0
    while True:
        print(node.value)
        depth += 1
        if node.value == word:
            count = node.count
            break
        elif word < node.value:
            node = node.left
        elif word > node.value:
            node = node.right

    return depth, count

def main():
    print(search(tree, "a"))

answered Dec 18, 2014 at 22:30

pirelius

1291 gold badge4 silver badges13 bronze badges

Collectives™ on Stack Overflow

Python: search in binary search tree

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related