Solution to EPI 10.12.2

epi_10_12_2.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>
#include <cassert>
#include <limits>

using namespace std;

/******************** Solution Begin ***************************/

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

Node* ConstructHelper(int max_val, const vector<int>& array, int& idx) {
  const int kNum = array.size();

  if (idx >= kNum || array[idx] >= max_val)
    return 0;

  Node *root = new Node;
  root->data = array[idx++];
  root->left = root->right = 0;
  Node *current = root;

  while (idx < kNum && array[idx] < max_val) {
    if (array[idx] < current->data) {
      // Child
      current->right = ConstructHelper(current->data, array, idx);
    }
    else {
      // Ancestor
      Node *newroot = new Node;
      newroot->data = array[idx++];
      newroot->right = 0;
      newroot->left = root;
      root = current = newroot;
    }
  }

  return root;
}

Node* Construct(const vector<int>& array) {
  int idx = 0;
  return ConstructHelper(numeric_limits<int>::max(), array, idx);
}

/******************** Solution End ***************************/

Node *SlowConstructHelper(const vector<int>& array, int start, int end) {
  if (start > end)
    return 0;

  int m = start;
  for (int i = start+1; i <= end; i++) {
    if (array[i] > array[m])
      m = i;
  }

  Node *root = new Node;
  root->data = array[m];
  root->left = SlowConstructHelper(array, start, m - 1);
  root->right = SlowConstructHelper(array, m+1, end);
  return root;
}

Node *SlowConstruct(const vector<int>& array) {
  return SlowConstructHelper(array, 0, array.size()-1);
}

bool IsEqualTree(Node* tree1, Node* tree2) {
  if ((!tree1) && (!tree2))
    return true;

  if ((!tree1) || (!tree2))
    return false;

  return (tree1->data == tree2->data) && IsEqualTree(tree1->left, tree2->left)
    && IsEqualTree(tree1->right, tree2->right);
}

int main() {
  const int kNumRuns = 1000;
  const int kArraySize = 10000;

  for (int run = 0; run < kNumRuns; run++) {
    vector<int> array(kArraySize);
    for (int i = 0; i < kArraySize; i++)
      array[i] = i; // Uniqueness guaranteed

    random_shuffle(array.begin(), array.end());

    Node *root1 = Construct(array);
    Node *root2 = SlowConstruct(array);
    assert(IsEqualTree(root1, root2));
  }
  return 0;
}