/*
 * CS 106B Section 6
 * BinaryTree.cpp implements the BinaryTree class behavior
 * declared in BinaryTree.h.
 */
#include "BinaryTree.h"
#include "strlib.h"
using namespace std;


BinaryTree::BinaryTree() {
    m_root = NULL;
}

BinaryTree::~BinaryTree() {
    clear();
}

void BinaryTree::clear() {
    clear(m_root);
    m_root = NULL;
}

void BinaryTree::clear(TreeNode* node) {
    if (node != NULL) {
        clear(node->left);
        clear(node->right);
        delete node;
    }
}


void BinaryTree::add(int value) {
    add(m_root, value);
}

// Creates a balanced binary tree for simplicity
void BinaryTree::add(TreeNode*& node, int value) {
    if (node == NULL) {
        node = new TreeNode(value);
    } else {
        if (height(node->left) > height(node->right)) {
            add(node->right, value);
        } else {
            add(node->left, value);
        }
    }
}


int BinaryTree::height() {
    return height(m_root);
}

int BinaryTree::height(TreeNode* node) {
    if (node == NULL) {
        return 0;
    } else {
        return 1 + max(height(node->left), height(node->right));
    }
}

bool BinaryTree::isBST() {
    // TODO: finish me!
    return false;
}

void BinaryTree::limitPathSum(int max) {
    // TODO: finish me!
}

bool BinaryTree::isBalanced() {
    // TODO: finish me!
    return false;
}

void BinaryTree::completeToLevel(int k) {
    // TODO: finish me!
}

int BinaryTree::countLeftNodes()  {
    // TODO: finish me!
    return 0;
}

string BinaryTree::toString() {
    return toString(m_root);
}


string BinaryTree::toString(TreeNode* node) {
    if (node == NULL) {
        return "/";
    } else if (node->left == NULL && node->right == NULL) {
        return integerToString(node->data);
    } else {
        return "(" + integerToString(node->data) + ", "
                + toString(node->left) + ", " + toString(node->right) + ")";
    }
}


ostream& operator <<(ostream& out, BinaryTree& root) {
    out << root.toString() << endl;
    return out;
}
