Yield All Root-to-leaf Branches Of A Binary Tree

Sorry if this is a common question but I haven't found an appropriate answer for my particular problem. I'm trying to implement a walk method that walks a binary tree from its root

Solution 1:

Here's a modified variant of your code.

code.py:

#!/usr/bin/env python3import sys


classNode:
    def__init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def__repr__(self):
        returnf"{self.__class__.__name__}({self.data})"    @propertydefchildren(self):
        if self.left:
            yield self.left
        if self.right:
            yield self.right

    @propertydefis_leaf(self):
        return self.left isNoneand self.right isNonedeftraverse_preord(self, accumulator=list()):
        print("  On node:", self)
        accumulator.append(self.data)
        if self.is_leaf:
            yield accumulator
        else:
            for child in self.children:
                print("  Entering child:", child)
                yieldfrom child.traverse_preord(accumulator=accumulator)
                accumulator.pop()
                print("  Exiting child:", child)


defmain():
    root = Node(data="A",
                left=Node(data="B",
                          right=Node(data="C")
                         ),
                right=Node(data="D",
                           #left=Node(data="E"),#right=Node(data="F"),
                          )
               )
    for path in root.traverse_preord():
        print("Found path:", path)


if __name__ == "__main__":
    print("Python {:s} on {:s}\n".format(sys.version, sys.platform))
    main()

Notes:

• I refactored the code a bit (simplified, changed some identifier names, texts and other insignificant changes)
• children property:
  • None for a node's left or right attribute, means that the node has no child, so no point including it in the returned result
  • Since the question is involving yield, I turned it into a generator (instead of returning a tuple or list, ...). As a consequence, I had to add is_leaf, since a generator doesn't evaluate to False (even if empty)

Output:

[cfati@CFATI-5510-0:e:\Work\Dev\StackOverflow\q055424449]> "e:\Work\Dev\VEnvs\py_064_03.07.03_test0\Scripts\python.exe" code.py
Python 3.7.3 (v3.7.3:ef4ec6ed12, Mar 25 2019, 22:22:05) [MSC v.1916 64 bit (AMD64)] on win32

  On node: Node(A)
  Entering child: Node(B)
  On node: Node(B)
  Entering child: Node(C)
  On node: Node(C)
Found path: ['A', 'B', 'C']
  Exiting child: Node(C)
  Exiting child: Node(B)
  Entering child: Node(D)
  On node: Node(D)
Found path: ['A', 'D']
  Exiting child: Node(D)

What is wrong with your code?

It's the traverse recurring call (child.traverse(branch=branch)). It created a generator, but since that wasn't used (iterated on) anywhere, the function didn't actually called itself, resulting in the attempt of removing more elements than added (only 1: which is the root node). So, it turns out that you were almost there. All you have to do, is adding a yield from in front of it :). More details on [Python]: PEP 380 -- Syntax for Delegating to a Subgenerator.

Solution 2:

There is a great answer here

Copying their Python example:

""" 
Python program to print all path from root to 
leaf in a binary tree 
"""# binary tree node contains data field ,  # left and right pointer classNode: 
    # constructor to create tree node def__init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None# function to print all path from root # to leaf in binary tree defprintPaths(root): 
    # list to store path 
    path = [] 
    printPathsRec(root, path, 0) 

# Helper function to print path from root  # to leaf in binary tree defprintPathsRec(root, path, pathLen): 

    # Base condition - if binary tree is # empty return if root isNone: 
        return# add current root's data into  # path_ar list # if length of list is gre if(len(path) > pathLen):  
        path[pathLen] = root.data 
    else: 
        path.append(root.data) 

    # increment pathLen by 1 
    pathLen = pathLen + 1if root.left isNoneand root.right isNone: 

        # leaf node then print the list 
        printArray(path, pathLen) 
    else: 
        # try for left and right subtree 
        printPathsRec(root.left, path, pathLen) 
        printPathsRec(root.right, path, pathLen) 

# Helper function to print list in which  # root-to-leaf path is stored defprintArray(ints, len): 
    for i in ints[0 : len]: 
        print(i," ",end="") 
    print() 

# Driver program to test above function """ 
Constructed binary tree is  
      10 
    /   \ 
   8     2 
  / \   / 
 3   5 2 
"""
root = Node(10) 
root.left = Node(8) 
root.right = Node(2) 
root.left.left = Node(3) 
root.left.right = Node(5) 
root.right.left = Node(2) 
printPaths(root) 

# This code has been contributed by Shweta Singh. 

Gives:

10 8 3 10 8 5 10 2 2

You can give it letters like you have too:

root = Node("A") 
root.left = Node("B") 
root.right = Node("D") 
root.left.right = Node("C") 
printPaths(root) 

Gives:

A B C A D