Python implementation of Breadth-First Search on Binary Search Trees

Question

I am trying to write a BFS algorithm for a Binary Search Tree using Python3.

I first initialised the class, defined an insert method, and inserted some random numbers:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if data <= self.data:
            if self.left == None:
                self.left = Node(data)
            else:
                self.left.insert(data)
        else:
            if self.right == None:
                self.right = Node(data)
            else:
                self.right.insert(data)

root = Node(1)
root.insert(0)
root.insert(2)
root.insert(1.5)
root.insert(2.4)
root.insert(1.6)
root.insert(2.3)

Then, I tried to write a recursive BFS method:

    def inLineTraversal(self, queue=[]):
        if queue == []:   # Base condition
            return
        temp = queue
        for node in temp:
            print(node.data) 
            if node.left != None:
                queue.append(node.left)
            if node.right != None:
                queue.append(node.right)
            queue.pop(0)
        self.inLineTraversal(queue)

However, this produced 1,2,2.4,1.5,2.3,2.3,1.6 as opposed to the correct result of 1,0,2,1.5,2.4,1.6,2.3.

I later used a while loop to perform the BFS, which correctly produced 1,0,2,1.5,2.4,1.6,2.3:

    def inLineTraversal(self):
        queue = [self]
        while queue != []:
            s = queue.pop(0)
            print(s.data)
            if s.left != None:
                queue.append(s.left)
            if s.right != None:
                queue.append(s.right)

What was wrong with the recursive solution?

Thierry Lathuille · Accepted Answer · 2020-04-26 07:15:30Z

The problem is in this line:

temp = queue

This doesn't create a new copy of queue, as you probably expected, it just gives it an additional name temp - but both names refer to the same list.

So, further on, you iterate on this list while modifying it, which almost always leads to problems.

Just create a copy of your list, like :

temp = queue[:]

And everything works fine

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if data <= self.data:
            if self.left == None:
                self.left = Node(data)
            else:
                self.left.insert(data)
        else:
            if self.right == None:
                self.right = Node(data)
            else:
                self.right.insert(data)

    def inLineTraversalRecursive(self, queue=[]):
        if queue == []:   # Base condition
            return
        temp = queue[:]
        for node in temp:
            print(node.data) 
            if node.left != None:
                queue.append(node.left)
            if node.right != None:
                queue.append(node.right)
            queue.pop(0)
        self.inLineTraversal(queue)

    def inLineTraversalLoop(self):
        queue = [self]
        while queue != []:
            s = queue.pop(0)
            print(s.data)
            if s.left != None:
                queue.append(s.left)
            if s.right != None:
                queue.append(s.right)

root = Node(1)
root.insert(0)
root.insert(2)
root.insert(1.5)
root.insert(2.4)
root.insert(1.6)
root.insert(2.3)
root.inLineTraversalLoop()
print()
root.inLineTraversalRecursive([root])

Output:

The Rizzler · Accepted Answer · 2020-04-26 07:23:03Z

1

This is because you put self.inLineTraversal(queue) outside the for loop. Also this line temp = queue is redundant. So the correct code for your recursive inLineTraversal would be:

def inLineTraversal(self, queue=[]):
    if queue == []:   # Base condition
        return
    for node in queue:
        print(node.data) 
        if node.left != None:
            queue.append(node.left)
        if node.right != None:
            queue.append(node.right)
        queue.pop(0)
        self.inLineTraversal(queue) # inside of the for loop

I tested and ran this modified method, I got the result you expected: 1,0,2,1.5,2.4,1.6,2.3.

edited Apr 26, 2020 at 7:23

answered Apr 26, 2020 at 7:14

The Rizzler

5221 gold badge7 silver badges20 bronze badges

Comments

ajay gandhi · Accepted Answer · 2020-04-26 07:19:01Z

0

I can see 2 problems in your code
1.) In the InlineTraversal method, You are copying queue to temp array which is not the correct way for copying elements. You are doing shallow copy here. That means both the lists(Queue and Temp) will point to element in same memory location.

2.) You are removing the elements from list inside for loop. you are iterating over Temp list and removing element from queue list which are actually same lists. So, basically you are removing element from same list on which you are iterating which is not a good practice.

To Fix this, perform deep copy on queue list by using

temp = queue[:]

answered Apr 26, 2020 at 7:19

ajay gandhi

5634 silver badges13 bronze badges

Collectives™ on Stack Overflow

Python implementation of Breadth-First Search on Binary Search Trees

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related