Binary Tree

Abstract idea of a tree:
A tree is another data structure that you can use to store information. Unlike stacks and queues, which are linear data structures, trees are hierarchical data structures.
Saying that the structure of a tree is hierarchical means that things are ordered above or below other things. For example, the army is hierarchical, with generals above colonels, and colonels above lieutenants, etc.
Here is an example of a tree holding letters:
```
      tree
      ----
       j    <-- root
     /   \
    f      k  
  /   \      \
 a     h      z    <-- leaves
```
Tree Vocabulary
Let's now introduce some vocabulary with our sample tree... The element at the top of the tree is called the root. The elements that are directly under an element are called its children. The element directly above something is called its parent. For example, a is a child of f and f is the parent of a. Finally, elements with no children are called leaves.
Is k a leaf? Who is its parent?
How many parents can elements have?

Aside: If you were to draw the picture above upside down, it would look like a real tree, with the leaves at the top and the root at the bottom...However, we usually draw tree data structures as we've done above.

Uses
There are many reasons to use a tree to store information. One reason might be because you want to store information that naturally forms a hierarchy. For example, the file system on a computer:
```
file system
-----------
     /    <-- root
  /     \
...    home
      /    \
   ugrad    course
    /      /   |   \
  ...  cs101 cs112 cs113
```
Despite the hierarchical order of the structure of the tree, the order enforced on objects in the tree will depend on how we use the tree. This just means that unlike a stack whose operations are usually limited to push and pop, there are many different kinds of trees and ways to use them. Thus, this flexibility makes them more akin to linked lists.
Another reason to use a tree is because trees make some operations more efficient (we'll discuss that at some later time).
Recursive Data Structure
A tree can be viewed as a recursive data structure. Why? Remember that recursive means that something is defined in terms of itself. Here, this means that trees are made up of subtrees.
For example, let's look at our tree of letters and examine the part starting at f and everything under it...
```
      tree
      ----
       j
     /   \
    f      k  
  /   \      \
 a     h      z
```
Doesn't it look like a tree itself? In this subtree, what is f (recall our vocabulary)?
What about just z? Doesn't it look like a subtree?
Binary Trees
We can talk about trees where the number of children that any element has is limited. In the tree above, no element has more than 2 children. For the rest of this example, we will enforce this to be the case.
A tree whose elements have at most 2 children is called a binary tree.
Since each element in a binary tree can have only 2 children, we typically name them the left and right child.
Tree operations:
As mentioned, there are different kinds of trees (e.g., binary search trees, 2-3 trees, AVL trees, tries, just to name a few).
What operations we will need for a tree, and how they work, depends on what kind of tree we use. However, there are some common operations we can mention:
- Add:
  Places an element in the tree (where elements end up depends on the kind of tree).
  For example, Add(tree, i) might give:
```
      tree
      ----
       j    <-- root
     /   \
    f      k
  /   \      \
 a     h      z
        \
         i    <-- new leaf
```
- Remove:
  Removes something from the tree (how the tree is reorganized after a removal depends on the kind of tree).
  For example, Remove(tree, h) might give:
```
      tree
      ----
       j    <-- root
     /   \
    f      k
  /   \      \
 a     i      z
```
  Here, i moved up to take its place.
- IsMember:
  Reports whether some element is in the tree.
  For example, IsMember(tree, a) should give a true value and IsMember(tree, y) should give a false value.
Other operations may be necessary, depending on the kind of tree we use.
Tree representation in C:
Since we want to be able to represent a tree in C, how are we going to store this hierarchical structure?
Can we use an array?
Answer: Certainly! There are times when we can use an array to represent a tree.
However, we can also do something along the lines of a linked list. For example, just as linked list nodes hold one element and point to the next node...
```
 |
 v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------
```
we could have tree nodes that hold one element and point to their children...
```
 -----
 | j |
 |---|
 | | |
 /---\
v     v
```
So, our first example tree of letters would look something like:
```
           |
           v
         -----
         | j |
         |---|
         | | |
         /---\
        v     v
    -----     -----
    | f |     | k |
    |---|     |---|
    | | |     |0| |
    /---\     ----\
   v     v         v
-----   -----      -----
| a |   | h |      | z |
|---|   |---|      |---|
|0|0|   |0|0|      |0|0|
-----   -----      -----
```
Note that some nodes don't have a left and/or right child, so those pointers are NULL.
Also, just as we need a pointer to the first node to keep track of a linked list; here, we need a pointer to the root node to keep track of a tree.
Special case: Empty Tree
What about when the tree is empty. How do we represent an empty tree?
Answer: There are no nodes, so the pointer to the root should be NULL.
Data types for a tree:
Before we implement tree functions, we must decide how to use C types to implement the above representation for a tree. An additional constraint is that we want to use the ADT/CDT method of hiding details of a data structure. We'll stick with our simple example, a tree of characters.
As usual, we'll want our tree data structure in its own module.
Now, people will use our tree something like the following:
```
#include "tree.h"

...

treeADT t1, t2;
char ch;

...

/* Setup trees. */
t1 = TreeCreate();
t2 = TreeCreate();

TreeAdd(t1, 'a');
TreeAdd(t2, ch);

...

/* Cleanup trees. */
TreeDestroy(t1);
TreeDestroy(t2);
```
That means, we need to define:
- the ADT (abstract type that people using the tree need).
- the CDT (the part of the implementation that keeps track of the tree).
- the element type (to make it easy to change the type of things held in the tree).
- the node type (remember we are using nodes to hold the elements).
The organization of these types in the tree module files are as follows:
```
tree.h				tree.c
------				------
				#include "tree.h"

type-of-element			type-of-node

abstract-type-of-tree		concrete-type-of-tree
```
Note: We'll get the types from tree.h in tree.c since we always include the header for a module in the implementation (.c) part of the module.

Again, the interface (.h) for the tree will need to have a abstract type for the tree (for people to define tree variables) and the type of an element (for functional prototypes)...
The implementation (.c) is hidden from the user of a tree and will hold the types we need to implement the internals of the tree. In other words, we will store elements in nodes and the information needed to keep track of a tree made up of nodes will be held in the concrete type. (Remember that we isolate these types from users of the tree, i.e., they do not need to know how the tree is implemented. Furthermore, isolating these types will prevent them from being able to mess up the tree.)

Now we can fill in these types. Let's start bottom-up from the simplest type and work our way up through types that use the simpler types.
The type-of-an-element has already been determined:
```
typedef char treeElementT;
```
Next, elements of the tree are being stored in nodes. For our binary tree, nodes must contain an element and pointers to 2 possible children, the left one and the right one.
How do we define the type for a node with these 3 parts?
Answer: We can combine them into one type with a struct:
```
typedef struct treeNodeTag {
  treeElementT element;
  struct treeNodeTag *left, *right;
} treeNodeT;
```
Next, we need something that holds all the information needed to keep track of the tree. Since the nodes already hold any elements, the only thing that is missing is the pointer to the root node.
Since this pointer has to do with the implementation of the tree, it becomes part of the concrete-type-of-tree, struct treeCDT:
```
typedef struct treeCDT {
  treeNodeT *root;
} treeCDT;
```
Finally, we must fill in what the abstract-type-of-tree is (which is always a pointer to the CDT):
```
typedef struct treeCDT *treeADT;
```
So, we have the following:
```
tree.h                          tree.c
------				------
				#include "tree.h"

typedef char treeElementT;      typedef struct treeNodeTag {
				  treeElementT element;
				  struct treeNodeTag *left,
				                     *right;
				} treeNodeT;

typedef struct treeCDT		typedef struct treeCDT {
	*treeADT;		  treeNodeT *root;
				} treeCDT;
```
Tree functions:
Now that we have the types finished, let's implement one of the tree operations. The tree functions we'll need are:
For general tree operations:
- TreeAdd()
- TreeRemove()
- TreeIsMember()
Because we are programming in C (setup/cleanup):
- TreeCreate()
- TreeDestroy()
The one we'll implement is TreeIsMember(). In this membership function, we'll assume that the elements in a tree are in no particular order, i.e., this function will be for a general binary tree. (Certain kinds of trees have an order to their elements making this function easier.)
Testing membership example
Suppose we want to see if h is in the tree...
```
      tree
      ----
       j    <-- root
     /   \
    f      k
  /   \      \
 a     h      z    <-- leaves
```
The thing to do is start at the root...
1. The element at the root, j, is not the thing we want, so we'll have to look at the left and right subtrees. We'll start on the left.
2. The element at the root of the left subtree, f, is not the thing we want, so we have to check its subtrees. We'll start on the left again.
3. The left subtree's root is a (not what we want). Since we've exhausted that subtree, we should go back up to f and try its right subtree.
4. Finally, the root of the right subtree of f is h, the element we were looking for, so we can report that we found it.
You can see how the search would continue through the tree if we didn't find the element yet. Based on our example, the ability to backtrack (e.g., from a back to f) is critical.

Let's summarize what we did above in an algorithm.
Since a tree can be viewed as a recursive data structure, we can probably create an algorithm that is recursive. Recursion will also give us the ability to backtrack, which we need.
What it means for the algorithm to be recursive is that it will use itself.
IsMember(tree, value) [recursive]
1. If the tree is empty, return false.
2. Check to see if the element at the root is the one we want...
  If so, return true.
  If not..
  1. Check the left subtree with IsMember(left-subtree, value).
    If found, return true.
  2. Check the right subtree with IsMember(right-subtree, value).
    If found, return true.
3. return false.
Note: When we return false, it doesn't necessarily mean the element is not in the whole tree, just the subtree we are working on.

You can see that the base cases are when we exhaust a subtree or when we find the element.
We use the recursion to check subtrees (which are trees themselves).
TreeIsMember() function:
To perform IsMember recursively, we will start with the top-level tree and recurse on subtrees. This means that we need a single type to refer to both the top-level tree and all subtrees, i.e., a type that is present throughout the tree data structure.
```
an ADT
  |     --------
  +---> | root | a CDT
        |  |   |
        ---+----
           |
           v
         -----
         | j |
         |---|
         | | |
         /---\
        v     v
    -----     -----
    | f |     | k |
    |---|     |---|
    | | |     |0| |
    /---\     ----\
   v     v         v
-----   -----      -----
| a |   | h |      | z |
|---|   |---|      |---|
|0|0|   |0|0|      |0|0|
-----   -----      -----
```
We cannot use the ADT (or CDT) to refer to subtrees because there is only one ADT (and its CDT), and it refers to the top-level tree (see figure above). The only type that is appropriate is node pointer (treeNodeT *)--there are node pointers that point to the top-level tree (the root part of the CDT) and all subtrees (all the left and right pointers).
However, the user of the tree doesn't know about node pointers, only ADTs. So, TreeIsMember() will be a wrapper function that takes a tree via an ADT and passes the node pointer at the root along to a recursive function.
Wrapper IsMember
Remember that IsMember should return a true/false value. So, our wrapper function will look like the following:
```
/*
 * Report whether value is found in the tree.
 * Assume the tree is a general binary tree
 * (i.e., elements are in no special order).
 */
int TreeIsMember(treeADT tree,
                 treeElementT value)
{
  return RecIsMember(tree->root, value);
}
```
It just calls the recursive function RecIsMember() to do the checking.

Recursive IsMember function:

So, RecIsMember() gets access to the tree (and subsequent subtrees) via node pointers...

static int RecIsMember(treeNodeT *root,
                       treeElementT value);

Since it is a helper function that is not accessible via the interface, we make it static and prototype it in the implementation file.

Now, all it has to do is the following:

static int RecIsMember(treeNodeT *root,
                       treeElementT value)
{
  /* Make sure subtree not empty. */

  if (root == NULL)
    return 0;  /* Not found */

  /*
   * Check the value at the root of
   * the current subtree.
   */

  if (root->element == value)
    return 1;  /* Found! */

  /* Check left subtree. */

  if (RecIsMember(root->left, value))
    return 1;  /* Found in left subtree. */

  /* Check right subtree. */

  return RecIsMember(root->right, value);
}

Binary Tree

Tree Vocabulary

Uses

Recursive Data Structure

Binary Trees

Special case: Empty Tree

Testing membership example

Wrapper IsMember