Binary Tree (1

Binary Trees
A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree.


In C the binary tree is built with a node type like this
struct node
{
int data;
struct node* left;
struct node* right;
}

Lookup() function
Given a binary search tree and a "target" value, search the tree to see if it contains the target.
int lookup(node* root, int target)
{
if (root == NULL) return 0;
if (target == root->data) return 1;
if (target < root->data)
return(lookup(root->left, target));
else
return(lookup(root->right, target));
}
Note : The lookup() algorithm could be written as a while-loop that iterates down the tree. We leave this as a homework.


Insert()
By given a binary search tree and a number, we insert a new node with the given number into the tree in the correct place.

node* NewNode(int data)
{
node* node = new(node);
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
node* insert(node* node, int data) {
if (node == NULL)
return(newNode(data));
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);
return(node);
}
build123()
This is a very basic problem with a little pointer manipulation. (You can skip this problem if you are already comfortable with pointers.) Write code that builds the following binary tree

Write the code in three different ways...
a: by calling newNode() three times, and using three pointer variables
b: by calling newNode() three times, and using only one pointer variable
c: by calling insert() three times passing it the root pointer to build up the tree
// a: call newNode() three times
node* build123a()
{
node* root = newNode(2);
node* lChild = newNode(1);
node* rChild = newNode(3);
root->left = lChild;
root->right= rChild;
return(root);
}

// b-call newNode() three times, and use only one local variable
node* build123b()
{
node* root = newNode(2);
root->left = newNode(1);
root->right = newNode(3);
return(root);
}
/*
c-Build 123 by calling insert() three times.
Note that the 2 must be inserted first.
*/
node* build123c()
{
node* root = NULL;
root = insert(root, 2);
root = insert(root, 1);
root = insert(root, 3);
return(root);
}

size()
Given a binary tree, count the number of nodes in the tree.
int size(node* nod)
{
if (nod==NULL) return 0 ;
return(size(nod->left)+1+size(nod->right));
}
maxDepth()
Given a binary tree, compute its "maxDepth" -- the number of nodes along the longest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0.
int maxDepth(node* nod)
{
if (nod==NULL) return 0;
int lDepth = maxDepth(nod->left);
int rDepth = maxDepth(nod->right);
if (lDepth > rDepth) return(lDepth+1);
return(rDepth+1);
}