Traversing a binary tree in Python

Question

I am almost finished with a project that has us creating a dictionary class that utilizes a binary tree structure. I am however stuck on how to implement a method that prints out all the elements in the tree, I just don't have much experience with binary trees so its rather confusing on how to code it.

The method I am trying to figure out is a keys method, that will traverse the entire tree and return a list of all the keys. Someone I know has hinted that I should create a private helper function that recursively traverses the tree and keeps track of all the keys. I would like to create what is he is talking about but I have no earthly idea how to code it. Can anyone help me code this out? Figuring this out would pretty much finish it all up for me.

Here is my code so far. [Key:Value] pairs are tuples. I have coded it and also had some help from textbook examples to construct all you see here:

class DictWithTree:

    def __init__(self):
        self._element = None
        self._left = None
        self._right = None
        self._size = 0

    def isempty(self):
        if self._element == None:
            return True
        return False

    def __len__(self):
        return self._size

    def __contains__(self,key):
        path = self._tracePath(key)
        return path[-1]._size > 0

    def _tracePath(self,key): # taken from the textbook example and modified
        if len(self) == 0 or key == self._element[0]:
            return [self]   
        elif len(key) < len(self._element[0]):
            return [self] + self._left._tracePath(key)
        else:
            return [self] + self._right._tracePath(key)

    def __getitem__(self,key):
        if len(self) == 0:
            raise KeyError(key)   
        elif key == self._element[0]:
            return self._element[1]
        elif key < self._element[0]:
            return self._left[key]
        elif key > self._element[0]:
            return self._right[key]
        else:
            raise KeyError(key)

    def __setitem__(self,key,value):
        path = self._tracePath(key)
        endOfPath = path[-1]
        if endOfPath._element != None:       
            if endOfPath._element[0] == key: 
                endOfPath._element = key,value
        if endOfPath._size == 0: # a new element
            for location in path:
                location._size += 1
            endOfPath._element = key,value
            endOfPath._left = DictWithTree()
            endOfPath._right = DictWithTree()

    def clear(self):
        self._element = None
        self._left = None
        self._right = None
        self._size = 0

    def pop(self,key):
        value = self[key]
        self._remove(key)
        return value

    def popitem(self):     # returns the 'last' item in the dictionary,
        if self.isempty(): # (i.e. the largest key in the dictionary)
            return KeyError("There are no keys in the dictionary")
        elif self._right._element == None:
            return self._element
        else:   
            return self._right.popitem()                                   

    def _remove(self,key):
        path = self._tracePath(key)
        endOfPath = path[-1]
        if endOfPath._size > 0:
            for location in path:
                location._size -= 1
            if len(endOfPath._left) == 0:
                endOfPath._promoteChild(endOfPath._right)
            elif len(endOfPath._right) == 0:
                endOfPath._promoteChild(endOfPath._left)
            else:
                endOfPath._element = endOfPath._left.pop()

    def _promoteChild(self,child):
        self._element = child._element
        self._left = child._left
        self._right = child._right

Why are you using a tree you wrote yourself instead of a Python dict? — Will
– Will, Commented Apr 16, 2011 at 18:54
It is a project, that is what we are supposed to do. Create a dictionary that uses a binary tree. — Eric
– Eric, Commented Apr 16, 2011 at 19:02
I believe he stated that was what his project specification was. — ninjagecko
– ninjagecko, Commented Apr 16, 2011 at 19:02
If anyone can help, would be a godsend. There are other methods I have to implement but they all derive from getting this keys method finished. Probably only like 10-12 lines of code are stopping me from being done :D — Eric
– Eric, Commented Apr 16, 2011 at 19:08
@Eric You should accept one of these answers, or post your final solution if none of these answers were what you needed.... Of course, I am assuming you finished your project? — Jonathan
– Jonathan, Commented Jan 7, 2012 at 12:06

Andrey Martyanov · Accepted Answer · 2017-05-19 19:05:41Z

3

There is another solution for recursive in-order tree traversal using Python 3's yield from:

def traverse(tree):
    if tree.left is not None:
        yield from traverse(tree.left)

    yield tree.value

    if tree.right is not None:
        yield from traverse(tree.right)

print(list(traverse(tree_root)))

I think it's far more readable and conceptually simple. I hope it will be helpful to somebody.

answered May 19, 2017 at 19:05

Andrey Martyanov

1316 bronze badges

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

Comments

ninjagecko · Accepted Answer · 2011-04-16 19:15:08Z

All you need to do is create a helper method visitAllSubnodes(node) which does something to the current node, then recursively calls itself on the left and right subnodes. What visitAllSubnodes(node) does can be anything, in your case it could be something like print(node._element), but you can make your function wonderfully modular, e.g.

def visitAllSubnodes(node, whatToDoAtEachNode):
    whatToDoAtEachNode(node)
    visitAllSubnodes(node._left, whatToDoAtEachNode)
    visitAllSubnodes(node._right, whatToDoAtEachNode)

def printAllElements(node):
    visitAllSubnodes(node, lambda x:print(x))

To actually return something, you need to use the concept of higher order functions and closures. For example, you could make a function which defines a private personal accumulator (a list you add to), and another function to which that private personal accumulator belongs to, then return the function.

So for example, each time traversed the tree, you could invoke this higher order function, let's call it makeFunctionWhichKeepsTrackOfWhatHasBeenPassedIntoIt(), which returns a function that keeps track of what has been passed into it, as well as the accumulator. I'd give more info but that would be the point of the problem set. =)

highBandWidth · Accepted Answer · 2011-04-16 21:06:33Z

0

This should do it

def allKeys(d):
    toVisit = []
    toVisit.append(d)
    while (len(toVisit)>0):
        x = toVisit.pop()
        if x._element:
            yield x._element[0]
        if x._left:
            toVisit.append(x._left)
        if x._right:
            toVisit.append(x._right)

For in-order traversal, you need a recursive soln, as given in the wikipedia entry on tree traversal.

edited Apr 16, 2011 at 21:06

answered Apr 16, 2011 at 19:09

highBandWidth

17.4k23 gold badges87 silver badges132 bronze badges

2 Comments

Eric Over a year ago

Say you wanted to make it return a list with all the keys, how would I do that? I also have never used "yield" before or used generators. Right now, it just prints out "<generator object allKeys at 0x02BAE5F8>"

Eric Over a year ago

NM on the last comment, I have got it working. However, is there anything I could do to make it print in order? It seems to do the following: Root ---> Keys Larger than Root ---> Keys Smaller than Root

Bernhard Barker · Accepted Answer · 2013-10-20 22:51:45Z

0

For tree traversal, usually people do breadth first traversal (BFT) or depth first traversal (DFT).

In BFT you use a queue to memorize where you left off, in DFT you use the stack to memorize where you left off. If you know the nature of queue and stack, it is just a piece of cake to understand the BFT and DFT, otherwise please read Breadth-first search and Depth-first search, by the way, the code to traversal the tree is usually no more than 10 lines which prove how easy they are.

edited Oct 20, 2013 at 22:51

Bernhard Barker

55.7k14 gold badges111 silver badges143 bronze badges

answered Apr 16, 2011 at 19:14

Rn2dy

4,19012 gold badges45 silver badges59 bronze badges

Collectives™ on Stack Overflow

Traversing a binary tree in Python

4 Answers 4

Comments

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related