create max-tree in order N

Question

Let A be the array of n distinct integers. Let the index of the maximum element of A be m. Define the max-tree on A to be the binary tree on the entries of A in which the root contains the maximum element of A, the left child is the max-tree on A[0:m-1] and the right child is the max-tree on A[m+1:n-1]. Design an O(n) algorithm for building the max-tree.

In case I create a dummy example, it turns out that the array given is the INORDER traversal of the max-tree, for the given condition on the roots of the subtree, that they should be maximum.

Answer 1

It is indeed possible to do it in O(n) time. I have also attached test cases that compare my solution against a reference O(n log n) solution. To solve it:

A couple of observations:

1. The provided array is the inorder traversal of the tree in question.
2. The tree has the max heap property, i.e. a node cannot have an ancestor with a lesser value than itself.

Approach: We will traverse the input array from start till end and maintain a stack containing nodes with decreasing values (from bottom to top). This stack will contain the most recently constructed node at the top and the node with the maximum value (root) at the bottom.

As we move through the array:

1. If stack is empty, push this node onto the stack.
2. If stack is not empty and contains some nodes with values less than the current value, the largest of these values will be the left child of the current node. Keep popping values until the stack is empty or the top of stack contains a value > current value. This follows from observations #1 and #2.
3. The current node may be the right child of the node on top of the stack. We can assume this until we see a larger value.

Since each node is scanned and pushed onto the stack once, it is an O(n) time solution.

Here is the code. The main function creates a random array of 10,000 numbers and constructs the max-tree using the above O(n) algorithm and a naive O(n log n) solution. I do this 1000 times and assert that the two trees are equal.

#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;
}

Edit: An earlier version claimed that the tree is a max heap. Corrected it to "max heap property".