Some definitions

A tree is a set of nodes and edges where an edge connects two distinct node.

A tree has to satisfy three requirements:

• One node is identified as the root
• Every node c other than the root is connected by an edge to some other node p. p is called the parent and c is called the child.
• A tree is connected:
  • For every node n other than the root,
  • the parent of n or…
  • the parent of the parent of n or…
  • the parent of the parent … of n will be the room

Other useful terms:

Leaves: nodes with no children

Internal nodes: nodes that have children

Labels: data attached to a node

Ancestors of node n: n itself, the parent of n, the parent of the parent of n, etc. up to the root

Descendents of n: all the nodes that have n as an ancestor (which includes n)

subtree rooted at n: all of the descendents of n

Binary trees

A binary tree is a tree with at most two children for each node.

Definition:

(define-struct node (key left right))
;; A Node is a (make-node Nat BT BT)

;; A binary tree (BT) is one of:
;; * empty
;; Node