Why is my implementation of Iterative Deepening Depth-First Search taking as much memory as BFS?

Question

BFS requires O(b^d) memory, whereas IDDFS is known to run in only O(bd) memory. However, when I profile these two implementations they turn out to use exactly the same amount of RAM - what am I missing?

I'm using a Tree class with a branching factor or 10 to run the tests:

class Tree(object):
    def __init__(self, value):
        self.key = value
        self.children = [ ]

    def insert(self, value):
        if len(self.children) == 0:
            self.children = [ Tree(value) for x in range(10) ]
        else:
            for ch in self.children:
                ch.insert(value)

My implementation of iddfs:

def iddfs(t):
    for i in range(0,8):
        printGivenLevel(t, i)

def printGivenLevel(t, level):
    if not t:
        return
    if level == 1:
        pass
    elif level > 1:
        for ch in t.children:
            printGivenLevel(ch, level - 1)

BFS is

def bfs(t):
    currLevel = [t]
    nextLevel = []
    while currLevel:
        for node in currLevel:
            if node:
                nextLevel.extend([ x for x in node.children ])
        currLevel = nextLevel
        nextLevel = []

The code is not really doing anything, just looping through the whole tree. I'm using https://github.com/fabianp/memory_profiler to profile the code.

Answer 1

IDDFS's memory benefits only apply to an implicit tree, where nodes are generated as they're reached and discarded soon after. With a tree represented completely in memory, the tree itself already takes O(b^d) memory, and the memory required for either IDDFS or BFS is minor in comparison.