3. Advance

1. Tree using `pair` data structure

In Scheme, you can use pairs to build tree structures by defining each node in the tree as a pair. Here’s a basic approach to creating and manipulating binary trees using pairs:

1.1 Building a Binary Tree

A binary tree node can be represented as a pair where:

The car part holds the value of the node.
The cdr part is itself a pair, where the car of this second pair is the left subtree and the cdr is the right subtree.

Here’s how you might define a simple binary tree:

(define (make-node value left right)
  (cons value (cons left right)))

In this definition:

value is the value of the current node.
left is the left subtree (can be another node or () if there is no left child).
right is the right subtree (can be another node or () if there is no right child).

1.2 Example Tree

Consider a tree with the following structure:

You can represent this tree as follows:

(define tree
  (make-node 1
             (make-node 2
                        (make-node 4 '() '())
                        (make-node 5 '() '()))
             (make-node 3 '() '())))

1.3 Accessing Tree Elements

To access parts of the tree, you can use the car and cdr procedures:

car of the tree gives the root value.
cdr gives a pair where:
- car is the left subtree.
- cdr is the right subtree.

For example:

(define (root-value tree)
  (car tree))

(define (left-subtree tree)
  (car (cdr tree)))

(define (right-subtree tree)
  (cdr (cdr tree)))

1.4 Traversing the Tree

You can write recursive functions to traverse the tree. Here’s an example of an in-order traversal:

(define (in-order-traversal tree)
  (if (null? tree)
      '()
      (append (in-order-traversal (left-subtree tree))
              (list (root-value tree))
              (in-order-traversal (right-subtree tree)))))