CODEWITHSUNDEEP
pythonsearchbinary-search-tree
pirelius
pirelius

Reputation: 129

Python: search in binary search tree

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()

Upvotes: 0

Views: 3088

Answers (2)

pirelius
pirelius

Reputation: 129

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"))

Upvotes: 0

Scott Hunter
Scott Hunter

Reputation: 49803

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.

Upvotes: 1

Related Questions