Max Tree

maxtree.cpp

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

using namespace std;

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

/******************** Solution Begin ***************************/
Node* Construct(const vector<int>& array) {
  stack<Node*> S;

  for (auto&& x : array) {
    Node* node = new Node{x, nullptr, nullptr};

    while (!S.empty() && (S.top()->data < x)) {
      node->left = S.top();
      S.pop();
    }

    if (!S.empty()) {
      S.top()->right = node;
    }
    S.emplace(node);
  }

  Node* last_popped = nullptr;
  while (!S.empty()) {
    last_popped = S.top();
    S.pop();
  }

  return last_popped;
}

/******************** 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;
}