from tree import * def bigs(t): """Return the number of nodes in t that are larger than all their ancestors. >>> p = Tree(1, [Tree(4, [Tree(4), Tree(5)]), Tree(3, [Tree(0, [Tree(6)])])]) >>> bigs(p) 5 >>> q = Tree(1, [Tree(4, [Tree(4), Tree(5)]), Tree(3, [Tree(0, [Tree(2)])])]) >>> bigs(q) 4 """ def f(a, x): if a.label > x: return 1 + sum([f(b, a.label) for b in a.branches]) else: return sum([f(b, x) for b in a.branches]) return f(t, t.label - 1) def bigs_nonlocal(t): """Return the number of nodes in t that are larger than all their ancestors. >>> p = Tree(1, [Tree(4, [Tree(4), Tree(5)]), Tree(3, [Tree(0, [Tree(6)])])]) >>> bigs_nonlocal(p) 5 >>> q = Tree(1, [Tree(4, [Tree(4), Tree(5)]), Tree(3, [Tree(0, [Tree(2)])])]) >>> bigs_nonlocal(q) 4 """ n = 0 def f(a, x): nonlocal n if a.label > x: n += 1 for b in a.branches: f(b, max(a.label, x)) f(t, t.label - 1) return n # (a Tree t) -> (a list of Trees within t) def smalls(t): """Return the non-leaf nodes in t that are smaller than all their descendants. >>> a = Tree(1, [Tree(2, [Tree(4), Tree(5)]), Tree(3, [Tree(0, [Tree(6)])])]) >>> sorted([t.label for t in smalls(a)]) [0, 2] """ result = [] # (a Tree t) -> (the smallest value within t) # side-effect: perhaps add t to result def process(t): if t.is_leaf(): return t.label else: smallest = min([process(b) for b in t.branches]) if t.label < smallest: result.append(t) return min(smallest, t.label) process(t) return result