# Hierarchical Structures - Little-t Trees

## An Overview of Little-t Trees

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!

## Recursion with Little-t Trees

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.

### Pseudocode

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.

### The pair? Predicate

When 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.

### Real Code

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.


## Example: 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))


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)
(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!

## Example: 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)