[edit]
# Hierarchical Structures - Little-t Trees

## An Overview of Little-t Trees

## Recursion with Little-t Trees

### Pseudocode

### The

### Real Code

## Example:

## Example:

**Test Your Understanding**

Below is an unfinished definition of
## Takeaways

Let's discuss some general properties of little-t trees.
We've seen that structures like `(cons (list 1 2) (list 3 4))`

can be represented in a tree-like structure:

Little-t trees are composed of *branches* and *leaves*.
The tree above has five
**branches**; they correspond to the lines on the diagram above. Notice that a
branch can lead to a **subtree**—a tree that is contained within a larger tree.
In this case, the branch `((1 2) 3 4)`

contains the subtree `(1 2)`

.
A **leaf** has no branches connecting from it. The tree above has 4 leaves: `1`

, `2`

, `3`

, and `4`

.
Leaves are found at the "bottom" of the tree, also called the **fringe**.

Compared to trees in the real world, trees in computer science tend to be upside-down!

When working with trees, it is usually helpful to think recursively.
As an example, let's write a function `count-leaves`

that counts the number of leaves in a tree.

We'll start by informally outlining what our function will do in plain English.
This is called writing **pseudocode**. After we understand how our `count-leaves`

function
should behave, we'll write the actual Racket code for it. This is good general technique for
solving problems.

Recall how we defined `length`

, which finds the number of elements in a list:

`length`

of an empty list is 0.`length`

of a non-empty list`x`

is 1 plus the`length`

of the`cdr`

of`x`

.

The base case is the same for `count-leaves`

:

`count-leaves`

of an empty list is 0.

Our recusive case is slightly different though.
In `length`

, we are guaranteed that the `car`

of the list is a single element, so we count its length as 1.
But for `count-leaves`

, its `car`

may contain one or more trees, and so its length will not always be 1.
Therefore, we need to recursively find the `count-leaves`

of the `car`

of the tree as well! Our recursive call is therefore:

`count-leaves`

of a tree is the`count-leaves`

of the`car`

of the tree plus`count-leaves`

of the`cdr`

of the tree.

Eventually we will `car`

ourselves to the leaf of the tree, and so our second base case will be:

`count-leaves`

of a leaf is`1`

.

`pair?`

PredicateWhen we call `car`

on a tree, we have to determine if it returns another tree (a pair), or a leaf (a single element, technically known as an *atom*).
How do we check for it? Racket has a built-in predicate `pair?`

that tests if its argument is the result of a `cons`

. For example:

`(pair? (cons 1 2))`

returns`#t`

.`(pair? (cons 1 (cons 2 3)))`

returns`#t`

.`(pair? 2)`

returns`#f`

.`(pair? 'pear)`

returns`#f`

.`(pair? '())`

returns`#f`

.

Using `pair?`

and the pseudocode above,
we can write the complete code for `count-leaves`

:

```
(define (count-leaves x)
(cond ((null? x) 0) ;; is the tree is empty?
((not (pair? x)) 1) ;;is the tree a single element?
(else (+ (count-leaves (car x)) ;; else, call count-leaves on the car
(count-leaves (cdr x))))) ;; and cdr of x and add them up.
```

`scale-tree`

In Lesson 4, we saw the function `scale-list`

, which multiplies each
item in a list by a given numeric factor. We are going to write an analogous
function, `scale-tree`

, which accepts a deep list and a numeric factor and multiplies all elements in the deep list by that factor.

Here is an example call:

```
> (scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)) 10)
(10 (20 (30 40) 50) (60 70))
```

**Test Your Understanding**

Below is an unfinished definition of scale-tree. Which base case(s) do we need to correctly define `scale-tree`

?

```
(define (scale-tree tree factor)
(cond ;;Your answer here.
(else
(cons (scale-tree (car tree) factor)
(scale-tree (cdr tree) factor)))))
```

Now, try `scale-tree`

out in your interpreter with some examples of your own!

`deep-reverse`

Let's work on a problem with a similar structure.
This time, we want to write a function called `deep-reverse`

that reverses the order of all elements in a deep list.
For example:

```
> (define x (list (list 1 2) (list 3 4)))
((1 2) (3 4))
> (deep-reverse x)
((4 3) (2 1))
```

Notice that not only do `(1 2)`

and `(3 4)`

switch places, but their elements do as well.
`deep-reverse`

should also work for lists that do not contain other lists inside of it.

Below is an unfinished definition of

`deep-reverse`

.
Which recursive call(s) do we need in order to correctly define `deep-reverse`

?
```
(define (deep-reverse d-l)
(cond ((null? d-l) null)
;;Your answer here.
))
```

Try this out in your Racket interpreter!

Trees can contain subtrees, so recursion can be very helpful when solving problems involving trees.