// **************** problem 1 ********************

int IsLeaf(Tree * t)
// postcondition:  returns 1 if t is a leaf, else returns 0
{
    it (t != 0 && t->left == 0 && t->right == 0){
        return 1;
    }
    return 0;
}

int NonLeafCount(Tree * t)
// postcondition: returns # of non-leaves in t
{
    if (t == 0 || IsLeaf(t)){
        return 0;
    }
    else
        return 1 + NonLeafCount(t->left) + NonLeafCount(t->right);
    }
}

// **************** problem 2 ********************

Node * Tree2List(Tree * t)
// precondition:  t is binary search tree     
// postcondition: returns pointer to first node of linked list
//                whose node-values are sorted (i.e., same order
//                as inorder traversal of t     
{
    Node * list = 0;
    DoList(t,list);
    return list;
}

// **** several versions of code follow.  First is O(n), second
// **** is O(n log n)

void DoList(Tree * t, Node * & list)
// precondition: list points to sorted linked list

// postcondition: list points to first node of sorted linked list
//                values same as inorder traversal of t (coming
//                before any nodes already in list)
// note: O(n)     
{
    if (t != 0){
        DoList(t->right,list);
        list = new Node(t->info,list);
        DoList(t->left,list);
    }
}

void DoList(Tree * t, Node * & list)
// postcondition: list points to first node of sorted linked list
//                values same as inorder traversal of t
// note: O(n log n)     
{
    if (t != 0){
        DoList(t->left,list);
        Node * listRight = new Node(t->info);
        DoList(t->right,listRight->next);

        Node * temp = list;
        if (temp == 0){
            list = listRight;
        }
        else{
            while (temp->next != 0){
                temp = temp->next;
            }
            temp->next = listRight;         
        }
    }
}

// *********** this is O(n) requiring a temporary header node
Node * Tree2List(Tree * t)
// precondition:  t is binary search tree     
// postcondition: returns pointer to first node of linked list
//                whose node-values are sorted (i.e., same order
//                as inorder traversal of t     
{
    Node * list = new Node;            // temporary header node
    DoList(t,list);
    Node * temp = list->next;          // "real" list
    delete list;
    return temp;
}

void DoList(Tree * t, Node * & list)
// precondition: list points to last node of a linked list
     
// postcondition: list points to last node of sorted linked list
//                with same values as inorder t traversal     
{
    if (t != 0){
        DoList(t->left,list);
        list->next = new Node(t->info);
        list = list->next;
        DoList(t->right,list);
    }
}

// **************** problem 3 ********************

int HasPathSum(Tree * t, int target)
// postcondition: returns 1 if there exists root-to-leaf path in t
//                whose nodes sum to target, else returns 0     
{
    if (t != 0){
        if (t->left == NULL && t->right == NULL){     // it's a leaf
            return t->info == target;
        }
        else{
            return HasPathSum(t->left,target - t->info) ||
                   HasPathSum(t->right,target - t->info);
        }
    }
    return 0;
}


// **************** problem 4 ********************

int TreeDiameter(Tree * t)
// postcondition: returns diameter of tree t     
{
    int height;
    return DoDiameter(t,height);
}

int DoDiameter(Tree * t, int & height)
// postcondition: sets height to height of tree t,
//                returns diameter of tree t
{
    int diameter = 0;
    height = 0;            // default to empty tree
    
    if (t != 0){
        int leftHeight,rightHeight;
        
        int leftD = DoDiameter(t->left,leftHeight);
        int rightD = DoDiameter(t->right,rightHeight);
        
        height = max(leftHeight,rightHeight) + 1;
        diameter = max(leftD, max(rightD, leftHeight + rightHeight + 1));
    }
    return diameter;
}