Basic tree traversal

bst.cpp

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// Definition for binary tree
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}

    void Traverse(int order, int level = 0, const char dir = 'T') {
        if (0 == order)
            cout << level << ":" << dir << ":" << val << " ";

        if (left) {
            left->Traverse(order, level + 1, 'L');
        }

        if (1 == order)
            cout << level << ":" << dir << ":" << val << " ";

        if (right) {
            right->Traverse(order, level + 1, 'R');
        }

        if (2 == order)
            cout << level << ":" << dir << ":" << val << " ";

        return;
    }
};

namespace Solution {
    TreeNode* sortedArrayToBST(const vector<int> &A);
}

int main() {
    cout << "Hello, World!" << endl;
    std::vector<int> inp;

    inp.push_back(0);
    inp.push_back(1);
    inp.push_back(2);
    inp.push_back(3);
    inp.push_back(4);
    inp.push_back(5);
    inp.push_back(6);
    inp.push_back(7);
    inp.push_back(8);
    inp.push_back(9);
    inp.push_back(10);

    TreeNode* pHead = Solution::sortedArrayToBST(inp);
    assert(pHead);
    pHead->Traverse(0);
    cout << endl;
    pHead->Traverse(1);
    cout << endl;
    pHead->Traverse(2);
    cout << endl;

    return 0;
}

TreeNode* MakeBST(const vector<int> &A, size_t start, size_t end) {
    size_t mid = (start + end)/2;
    TreeNode *pNode = new TreeNode(A[mid]);

    if (mid > start) {
        pNode->left = MakeBST(A, start, mid - 1);
    }

    if (mid < end) {
        pNode->right = MakeBST(A, mid + 1, end);
    }

    return pNode;
}

TreeNode* Solution::sortedArrayToBST(const vector<int> &A) {
    // Do not write main() function.
    // Do not read input, instead use the arguments to the function.
    // Do not print the output, instead return values as specified
    // Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details

    return A.empty() ? NULL : MakeBST(A, 0, A.size()-1);
}