Trees

Sequence Aggregation

Iterable : an object capable of returning its members one at a time

several built-in functions take iterable arguments and aggregation them into a value :

-   sum ( iterable [, start] ) -> value

-   max ( iterable [, key = func ] ) -> value or max -> value

More sequence aggregation

-   bool ( any_value ) -> bool

: take in any value (not only iterables) and returns True if the value is a True value and False if it is a False value.

-   all ( iterable ) -> bool

: returns Ture if bool(x) is True for all values x in the iterable. If the iterable is empty, return True. In other words, check if all values in the iterable are true values

-   any ( iterable ) -> bool

: returns True if bool(x) is True for at least one value x in the iterable. If the iterable is empty, return False. In other words, check if any values in the iterable are true values

 

Trees

Tree Abstraction

Recursive Description ( wooden trees ) : a tree has a root and a list of branches, each branch is a tree, a tree with zero branches is called a leaf

Relative Description ( family trees ) : each location in a tree is called a node, each node has a label value, one node can be the parent / child of another

Tree Abstraction Implementation

Tree Processing

Tree Processing uses Recursion

: just like checking for whether the branches were trees, we also use recursion in tree processing functions

1. the base case is the smallest version of the problem, many times if its a leaf

2. the recursive call happens on smaller subproblems, which tend to be branches

3. we use the recursive calls with some type of aggregation afterwards to get our final solution

Count Nodes in a Tree

: we want to count how many nodes there are in this tree _ try recursively

Collect the Leaves

: gather all the leaf values from this tree _ tackle this recursively _ notice that aggression this time only requires the recursive calls; it does not involve the original root

Print Tree

: sor far, trees appear as ensted lists ( because that is what they are underneath the abstraction barrier ). Let's implement a function that prints out the tree more visually

Creating Trees

: a function that creates a tree from another tree is typically also recursive

: create a function that returns a new tree with every value squared

The Recursive Process

-   Recursively create the squared subtree

-   Recursively create the next squared subtree

-   Join the two new subtrees with the root values squared

Fib Tree

Tree Recursion vs Tree Problems

-   Tree Recursion : recursive function with multiple recursive calls

-   Tree problems : problems dealing with Trees

-   Tree problems that use recursion in their solutions are a form of tree recursion problems