Getting an iterator for traversing a binary tree using depth first

Question

I want to do a depth first traversal of a binary tree using a for loop and perform calculations at each step.

Lets say you have a tree of 4 levels:

       root
       /  \
      /    \
     /      \
    xx       xx
   /  \     /  \
  /    \   /    \
xx    xx   xx    xx
/ \   / \  / \   / \
x  x x   x x  x  x  x

If you put the "steps of the depth first exploration of the tree" in a list it would look like this:

[
[1],
[1,1], 
[1,1,1],
[1,1,0],
[1,0],
[1,0,1],
[1,0,0],
[0], 
[0,1],
[0,1,0], 
[0,1,1],
[0,0],
[0,0,1]
[0,0,0] 
]

Is there a function that given the levels of a binary tree returns the "steps of the tree exploration" in a list?

My first though was to use the itertools.permutationlibrary but it doesn't give you the right order.

I also tried using:

l = [False, True]
list(itertools.product(l, repeat=3))

Close but it doesn't take into account that I'm going up and down the levels of the tree.

Answer 1

Assuming your binary tree is a perfect binary tree, you could use this function:

def traverse(height, left=1, right=0):
    path = []
    while True:
        if len(path) < height:
            path.append(left)
        else:
            while path[-1] == right:
                path.pop()
                if not path:
                    return
            path[-1] = right
        yield path

Then call it as follows for a tree with height 3:

for path in traverse(3):
    print(path)