CODEWITHSUNDEEP
pythonqueuebinary-search-treebreadth-first-search
PyGuy
PyGuy

Reputation: 33

Breadth First Search on a Binary Search Tree in Python

I've been working on building different data types and applying various sorting algorithms to them. I'm currently working on a breadth-first search on a binary search tree. My code is pretty much the same as what you'll find everywhere online, yet it consistently prints my values twice, and I'm now mind boggled. Any guidance would very much appreciated. 

# Remove (dequeue) function for Queue class
def remove(self, current=''):
    if current == '':
        current = self.tail
    # start looping/recurring to find the front of the queue
    if current.next:
        if current.next.next:
            current = current.next
            return self.remove(current)
            # side note - I'm doubting the usefulness of recursion here
        else:
            n = current.next.value
            current.next = None
            self.size -= 1
            return n
    elif current == self.tail:
        if current.value:
            n = current.value
            current = None
            self.size -= 1
            # print("Queue is now empty - returning final number")
            return n
        else:
            return "Queue is already empty."
    else:
        raise ValueError("mind boggling error...") #never raised

# Add (enqueue) function for my queue:
def add(self,value):
    n = Node(value) # create the new node we're adding
    n.next = self.tail # point the new node to link to the old tail
    self.tail = n # now have the tail point to the new node
    self.size += 1


# Breadth First Search function for the Binary Search Tree
def bfs(self):
    """
    This is currently VERY inefficient from a memory
    standpoint, as it adds a subtree for EACH node...right?
    or is it just the names/addresses of the objects being stored in
    each node, and each node is still only in the same memory location?
    """
    queue = Queue()
    queue.add(self)
    while queue.size > 0:
        current = queue.remove()
        print(current.value)

        if current.left_child:
            queue.add(current.left_child)
        if current.right_child:
            queue.add(current.right_child)

# how I typically test:
bst = BinarySearchTree(50)
for i in range(1,10):
    bst.insert_node(i*4)
bst.bfs()

Sample Output: 25 25 4 28 4 28 8 32 8 32 12 36 12 36 16 16 20 20 24

Seeing as it prints the root node twice on its own and then both children nodes twice as a pair, one after the other, suggests it's working in the sense of going in the right order level by level, but it double prints left and right child together, until it doesn't, as can see that towards the end it starts printing twice back-to-back instead if in pairs, and it cuts out before printing 24 a 2nd time.

I should also make the disclaimer that I have no interest in using python lists in my queue functions. The whole point of this exercise is to manually build my data structures w/o help from using pre-built ones beyond ints/strings.

The full file is available on my GitHub at https://github.com/GhostlyMowgli/data_structures_plus

Again, any help here would be so much appreciated.

Upvotes: 1

Views: 1504

Answers (1)

Snark
Snark

Reputation: 1664

Your issue is in your queue.remove functionality, below is the fixed code with a marker on the offending line (219)

  def remove(self, current=''):
    if current == '': 
        current = self.tail
    if current.next:
        if current.next.next:
            current = current.next
            return self.remove(current) # recursive - keep going to front
        else:
            n = current.next.value
            current.next = None
            self.size -= 1
            return n
    elif current == self.tail:
        # now I'm wondering if this is even smart
        # shouldn't I be checking if current is a None type?!?!
        if current.value:
            n = current.value
            self.tail = None # HERE!!!! NOT current = None
            self.size -= 1
            # print("Queue is now empty - returning final number")
            return n
        else:
            return "Queue is already empty."
    else:
        raise ValueError("mind boggling coding error...")

Upvotes: 1

Related Questions