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.

please explain the contents of your "tree Exploration list" I understand a 1 = visited & 0 indicates not visited, but how do the positions relate to the traversal? — itprorh66
– itprorh66, Commented Mar 19, 2022 at 14:16
@itprorh66 for example: [1,1,0] indicates left on first level, left on second, and right on third. — dank
– dank, Commented Mar 19, 2022 at 14:56

trincot · Accepted Answer · 2022-03-20 09:24:21Z

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)

answered Mar 20, 2022 at 9:24

trincot

357k38 gold badges282 silver badges338 bronze badges

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

Collectives™ on Stack Overflow

Getting an iterator for traversing a binary tree using depth first

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related