1

I'm trying to write a code that traverses a general tree height by height from the root of the tree. What I'm trying to write is something that prints a list where the root is at index[0] followed by the children of the root and then their children. I'm trying to write it so it repeats this process for each subtree until it reaches the bottom of the tree. This is the design code that I have but I can't figure out how to write it in python. 

def traversal(tree):
    if tree is empty:
        print("No tree to traverse")
    else:
        starting at the root print a list containing the root at [0], its 
        children, and its grand children 
    recursively call function
    set new root to child of root 
    traverse each subtree until bottom of tree
Prune
  • 76,765
  • 14
  • 60
  • 81
marty_mcfly
  • 51
  • 4
  • That is **Breadth-first search** – Ṃųỻịgǻňạcểơửṩ Apr 30 '18 at 22:39
  • possible duplicate: https://stackoverflow.com/questions/2358045/how-can-i-implement-a-tree-in-python-are-there-any-built-in-data-structures-in – anishtain4 Apr 30 '18 at 22:49
  • I think your pseudocode is a bit confused. If recursively print out one sub-tree before starting on the next one, you'll get a depth-first traversal, since the leaf nodes of the first sub-tree will get printed out before the top nodes of the other subtrees. If you really want all elements of the same depth to be printed out together, then you need to keep track of all the nodes at a given level together (e.g. by adding them to a list). Recursion is more natural for DFS than BFS, due to the nature of the recursive stack (DFS needs a stack anyway, BFS wants a queue). – Blckknght Apr 30 '18 at 23:14

0 Answers0