Recursion and Tree Assignment

binary-search-tree.cpp

#include <iostream>
#include <vector>
#include <iomanip>


using namespace std;

struct myInt
{
    int num;
};

struct treeNode
{
    int data;
    treeNode *left, *right;
};

treeNode* getNewTreeNode(int value = 0, treeNode* left = NULL, treeNode* right = NULL)
{
    treeNode* Node = new treeNode;
    Node->data = value;
    Node->left = left;
    Node->right = right;
    return Node;
}

treeNode* insertBST(treeNode* Node, int value, myInt* lc = NULL)
{

    if(lc != NULL)
    {
        lc->num = lc->num + 1;
        //cout<<endl<<value<<" lc = "<<lc->num<<endl;
    }

    if(Node == NULL)
    {
        Node = getNewTreeNode(value);
    }
    else if(value > Node->data)
    {
        Node->right = insertBST(Node->right,value,lc);
    }
    else
    {
        Node->left = insertBST(Node->left,value,lc);
    }

    return Node;
}


void BST_preorder(treeNode* Node, vector<int> *vec = NULL)
{
    if(Node->left != NULL)
    {
        BST_preorder(Node->left,vec);
    }

    if(vec == NULL)
    {
        cout<<Node->data<<" ";
    }
    else
    {
        vec->push_back(Node->data);
    }

    if(Node->right != NULL)
    {
        BST_preorder(Node->right,vec);
    }

    return;
}

void BST_postorder(treeNode* Node, vector<int> *vec = NULL)
{
    if(Node->left != NULL)
    {
        BST_postorder(Node->left,vec);
    }
    if(Node->right != NULL)
    {
        BST_postorder(Node->right,vec);
    }

    if(vec == NULL)
    {
        cout<<Node->data<<" ";
    }
    else
    {
        vec->push_back(Node->data);
    }

    return;
}

void BST_inorder(treeNode* Node, vector<int> *vec = NULL)
{
    if(vec == NULL)
    {
        cout<<Node->data<<" ";
    }
    else
    {
        vec->push_back(Node->data);
    }

    if(Node->left != NULL)
    {
        BST_inorder(Node->left,vec);
    }
    if(Node->right != NULL)
    {
        BST_inorder(Node->right,vec);
    }
    return;
}

treeNode* findNode(int value, treeNode* root)
{
    treeNode* found = root;

    if(found == NULL)
    {
        return NULL;
    }
    else if(found->data == value)
    {
        return found;
    }

    if(value > found->data)
    {
        found = findNode(value,found->right);
    }
    else
    {
        found = findNode(value,found->left);
    }

    return found;
}


int findDepth(treeNode* root)
{
    vector<int> vec;

    BST_inorder(root,&vec);

    treeNode* mTree = NULL;

    int max = 0;

    myInt* count = new myInt;

    for(unsigned int i = 0; i < vec.size(); i++)
    {
        count->num = 0;

        mTree = insertBST(mTree,vec[i],count);

        //cout<<vec[i]<<" "<<count->num<<endl;

        if(max<count->num)
        {
            max = count->num;
        }
    }

    return max;
}


//BSTprettyprint FROM Stack Overflow for easy visuals
// http://stackoverflow.com/questions/3899636/how-can-i-print-a-binary-tree-search-class-vertically

void BSTprettyprint(treeNode* n, int pos = 0){
    if (n==NULL) {
        for(int i = 0; i < pos; ++i)
            cout << "\t";
        cout << 'X' << endl;
        return;
    }
    BSTprettyprint(n->right,pos+1);
    for(int i = 0; i < pos; i++)
        cout << "\t";
    cout << n->data << endl;
    BSTprettyprint(n->left,pos+1);
}

int main()
{
    treeNode* root = NULL;

    int treeData[] = {7,12,13,20,5,6,11,2,1,3,19,25,21,22};

    int tDsize = sizeof(treeData)/sizeof(int);

    for(int i = 0; i < tDsize; i++)
    {
        root = insertBST(root,treeData[i]);
    }

    cout<<endl<<"------------------------------------------"<<endl;
    BSTprettyprint(root);
    cout<<endl<<"------------------------------------------"<<endl;


    cout<<endl<<"Pre order: "<<endl;
    BST_preorder(root);

    cout<<endl<<"Post order: "<<endl;
    BST_postorder(root);

    cout<<endl<<"in order: "<<endl;
    BST_inorder(root);


    cout<<endl<<"Find which value?";

    int tmp;
    cin>>tmp;

    treeNode* findResult = findNode(tmp,root);
    if(findResult != NULL)
    {
        cout<<"Found!, pointer at =>"<<findResult<<endl;
    }
    else
    {
        cout<<"Not found! Sorry"<<endl;
    }

    cout<<endl<<"DEPTH IS:  "<<findDepth(root)<<endl;

    return 0;
}

print-fibonacci-recursive.cpp

#include <iostream>

using namespace std;

void printFibo(int size = 25, int bp = 1,int p = 1)
{
    if(size <= 0)
    {
        return;
    }

    cout<<bp<<" "<<p<<" ";

    printFibo(size-2, bp+p , p + (bp+p));

}

int main()
{
    printFibo();

    return 0;
}

recursive-digit-adder.cpp

#include <iostream>

using namespace std;

int sumDigits(int num)
{
    if(num/10 == 0)
    {
        return num;
    }
    else
    {
        return ((num%10)+sumDigits(num/10));
    }
}

int main()
{
    int input;
    cin>>input;

    cout << sumDigits(input) << endl;
    return 0;
}

recursive-fact.cpp

#include <iostream>

using namespace std;

int findFact(int num)
{
    if(num == 1)
    {
        return num;
    }
    else
    {
        return (num + findFact(num-1));
    }
}

int main()
{
    int input;
    cin>>input;

    cout << findFact(input) << endl;
    return 0;
}