Three kinds of traverse binary tree.

change print to yield / yield from

def transverse(root):
    if not root:
        return
    yield from transverse(root.left)
    yield root.val
    yield from transverse(root.right)

we can write

for val in transverse(root):
    print(val)

Here we find that a complex recursive traversal is turned into a "tiling”

What are the applications?

Find the max of binary tree

max(transverse(root))

min

min(transverse(root))

sum a tree

sum(transverse(root))

Space $O(1)$ , But it feels like $O(n)$ traverse an array.

RIIR

Rust Playground

ref:

r/rust - Comment by u/[deleted] on "How to iterate trees nicely?"