CS 12 SI w8

#include <iostream>
#include <vector>
using namespace std;

//Binary node structure
struct BinaryNode {
    int data;
    BinaryNode* left;
    BinaryNode* right;
    BinaryNode(int data) : data(data), left(0), right(0) {}
};

//Generate a binary tree given a vector of integers. Return the root of the tree
BinaryNode* generateBinaryTree(vector<int> data);

//Add a single element to a binary tree if it doesn't exist in the tree already.
//Return true if successfully added and false otherwise
bool addToTree(BinaryNode* root, int data);

//Returns a pointer to a node withe a given data value, otherwise return a
//null pointer.
BinaryNode* findElement(BinaryNode* root, int data);

//Output nodes in the order of: left subtree, current node, right subtree.
void inOrderTraversal(BinaryNode* root);

//Reverses a binary tree
void reverseTree(BinaryNode* root);


int main() {
//---------------------------------------------------------------------------
    //Problem 1: Draw a diagram that shows the structure of the tree generated
    //           below.
    vector<int> v {5, 2, 8, 1, 3, 6, 9, 2};
    BinaryNode* root = generateBinaryTree(v);
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
    //Problem 2: Complete the implementation of the function findElement
    //           so that the following code works correctly.

    cout << "PROBLEM 2 OUTPUT" << endl;

    //The following should output: "NULL 1 2 3 NULL 5 6 NULL 8 9"
    for (int i = 0; i < 10; ++i) {
        BinaryNode* elem = findElement(root, i);
        if (elem) {
            cout << elem->data << ' ';
        }
        else {
            cout << "NULL" << ' ';
        }
    }
    cout << endl << endl;
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
    //Problem 3: Implement an "in order traversal." What that means is that our
    //           algorithm will visit every node by first visiting the left node
    //           then the root node, then the right node. To test if it works
    //           try printing out the nodes in the order your algorithm visits
    //           them.

    cout << "PROBLEM 3 OUTPUT" << endl;

    //The following code should output: 1 2 3 5 6 8 9
    inOrderTraversal(root);

    cout << endl << endl;
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
    //Challenge Problem: The following problem is often asked as an interview
    //                   question: Given a binary tree, write a function to
    //                   reverse the binary tree. Below is a simple illustration
    //                   of what it means to reverse a binary tree.

    //           1                             1
    //         /   \                         /   \
    //        2     3           =>          3     2
    //       / \   / \                     / \   / \
    //      4   5 6   7                   7   6 5   4

    cout << "CHALLENGE PROBLEM OUTPUT" << endl;

    //The following code should output:
    //    9 8 6 5 3 2 1
    //    1 2 3 5 6 8 9

    for (int i = 0; i < 2; ++i) {
        reverseTree(root);
        inOrderTraversal(root);
        cout << endl;
    }
//---------------------------------------------------------------------------

    return 0;
}

BinaryNode* generateBinaryTree(vector<int> data) {
    BinaryNode* head = new BinaryNode(data.at(0));
    for(int i = 1; i < data.size(); ++i) {
        addToTree(head, data.at(i));
    }
    return head;
}

bool addToTree(BinaryNode* currentNode, int data) {
    if (data < currentNode->data) {
        if (currentNode->left) {
            return addToTree(currentNode->left, data);
        }
        currentNode->left = new BinaryNode(data);
        return true;
    }
    if (data > currentNode->data) {
        if(currentNode->right) {
            return addToTree(currentNode->right, data);
        }
        currentNode->right = new BinaryNode(data);
        return true;
    }
    return false;
}

//Stub for Problem 2
BinaryNode* findElement(BinaryNode* root, int data) {
    return 0;
}

//Stub for Problem 3
void inOrderTraversal(BinaryNode* root) {
    return;
}

//Stub for Challenge Problem
void reverseTree(BinaryNode* root) {
    return;
}