CODEWITHSUNDEEP
pythonlisttreetraversal
Tyrange Denhops
Tyrange Denhops

Reputation: 37

Breadth First Search does not return the correct ordering for nodes

I have implemented a tree that looks like this :

               1

    2          3          4

 5     6               7      8

I want to print it Breadth wise. This is my code :

class Node:
    def __init__(self):
        self.data = None
        self.children = []


class Tree:
    def __init__(self):
        self.root = Node()

    def build(self):
        self.root.data = 1
        self.root.children.append(Node())
        self.root.children.append(Node())
        self.root.children.append(Node())
        self.root.children[0].data = 2
        self.root.children[1].data = 3
        self.root.children[2].data = 4

        self.root.children[0].children.append(Node())
        self.root.children[0].children.append(Node())

        self.root.children[2].children.append(Node())
        self.root.children[2].children.append(Node())

        self.root.children[0].children[0].data = 5
        self.root.children[0].children[1].data = 6

        self.root.children[2].children[0].data = 7
        self.root.children[2].children[1].data = 8
        return


    def traverseBF(self, node):
        li = []
        trav = []
        li.append(node)
        while len(li) != 0:
            for x in li:
                trav.append(x.data)
                for z in x.children:
                    li.append(z)
                # map(lambda z: li.append(z), x.children)
                li.remove(x)
        print(trav)



t = Tree()
t.build()
t.traverseBF(t.root)

The Ouput is : [1, 3, 2, 5, 4, 7, 6, 8]

My Questions are :

  1. Why is 3 getting inserted in trav[] before 2, even though in root.children the order is [2,3,4]
  2. Why does the commented out map function does not give the same results as the for loop above it ?

Upvotes: 1

Views: 106

Answers (1)

cs95
cs95

Reputation: 402633

The issue is with how you manage your queue. Use a single while loop which checks for the length of the list. Inside the while, pop the first node, then extend the queue with the popped node's children. Your function should look like this:

def traverseBF(self, node):
    li = []
    trav = []
    li.append(node)
    while len(li) != 0:
        x = li.pop(0)          # pop the first item
        li.extend(x.children)  # extend the queue with children
        trav.append(x.data)
    print(trav)

With this, t.traverseBF(t.root) prints [1, 2, 3, 4, 5, 6, 7, 8].

Here's a "cleaner" version of your code. I like generators so I turned this into a generator that returns the node values in BFS order one by one:

def bfs(node):
    q = [node]
    while q:
        n = q.pop(0)
        q.extend(n.children)
        yield n.data

[*bfs(t.root)]
# [1, 2, 3, 4, 5, 6, 7, 8]

Upvotes: 1

Related Questions