Implementing DFS and BFS for binary tree

Question

I'm trying to traverse a binary tree using depth first traversal and breadth first traversal, but I'm running into trouble. My node and tree implementation seems to be fine, I'm just not sure how to properly traverse the tree depth-wise and breadth-wise.

class Node:
    def __init__(self, val):
        self.l = None
        self.r = None
        self.v = val

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

    def getRoot(self):
        return self.root

    def add(self, val):
        if(self.root == None):
            self.root = Node(val)
        else:
            self._add(val, self.root)

    def _add(self, val, node):
        if(val < node.v):
            if(node.l != None):
                self._add(val, node.l)
            else:
                node.l = Node(val)
        else:
            if(node.r != None):
                self._add(val, node.r)
            else:
                node.r = Node(val)

    def find(self, val):
        if(self.root != None):
            return self._find(val, self.root)
        else:
            return None

    def _find(self, val, node):
        if(val == node.v):
            return node
        elif(val < node.v and node.l != None):
            self._find(val, node.l)
        elif(val > node.v and node.r != None):
            self._find(val, node.r)

    def printTree(self):
        if(self.root != None):
            self._printTree(self.root)

    def _printTree(self, node):
        if(node != None):
            self._printTree(node.l)
            print(str(node.v) + ' ')
            self._printTree(node.r)

    # This doesn't work - graph is not subscriptable
    def dfs(self, graph, start):
        visited, stack = set(), [start]
        while stack:
            vertex = stack.pop()
            if vertex not in visited:
                visited.add(vertex)
                stack.extend(graph[vertex] - visited)
        return visited

     # Haven't tried BFS.  Would use a queue, but unsure of the details.

Here's a hint. For BFS, a queue is most appropriate, while for DFS, you can use a stack. — Neel
– Neel, Commented Apr 24, 2016 at 18:51
@Neel OP is aware of DFS/BFS implementations - they have written code for the same as a method. The specific issue is that it seems they are trying to make their graph subscriptable. — Akshat Mahajan
– Akshat Mahajan, Commented Apr 24, 2016 at 19:00

user2390182 · Accepted Answer · 2017-10-20 18:24:05Z

14

If it is a tree, visited can be a list since trees are non-circular, so there no need to check whether you have visited a node before and, more importantly, you want to maintain the order of your traversal.

def dfs(self, tree):
    if tree.root is None:
        return []
    visited, stack = [], [tree.root]
    while stack:
        node = stack.pop()
        visited.append(node)
        stack.extend(filter(None, [node.r, node.l]))  
        # append right first, so left will be popped first
    return visited

edited Oct 20, 2017 at 18:24

answered Apr 24, 2016 at 19:15

user2390182

73.7k6 gold badges71 silver badges95 bronze badges

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

1 Comment

user1767754 Over a year ago

This is a really good side note, probably as well the right answer!

Akshat Mahajan · Accepted Answer · 2020-07-16 16:13:41Z

Your DFS implementation is slightly incorrect. As written, you've actually mimicked a queue, not a stack.

Your current code actually works fairly well for breadth-first search. It forces the siblings of a node to be evaluated before its children:

def bfs(self, graph, start):
    visited, queue = set(), [start]
    while queue:
        vertex = queue.pop()
        if vertex not in visited:
            visited.add(vertex)
            # new nodes are added to end of queue
            queue.extend(graph[vertex] - visited)
    return visited

The logic for DFS requires a stack to behave like this: when a new node comes, you need to add it to the left of the list, rather than the right. This way, you force the traversal of a node's descendants before the node's siblings.

def dfs(self, graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            # new nodes are added to the start of stack
            stack = graph[vertex] - visited + stack 
    return visited

Other Issues

The specific issue you are facing beyond this is that you haven't specified what graph is.

If graph is an object that doesn't support lookup, then you could implement that using a __getitem__() method in the class definition.

Typically, people are content to use a dictionary to implement this. Something like {Node: [<list of node's children], ... } should more than suffice.

Collectives™ on Stack Overflow

Implementing DFS and BFS for binary tree

2 Answers 2

1 Comment

Other Issues

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Other Issues

Comments

Your Answer

Sign up or log in

Post as a guest

Related