/* Checking if a tree is indeed a tree 

This code is assumed to exist in the "node<ST>" class containing left
and right pointers to subtrees.
*/

  // testing if x already occurs in V:
  static bool memb(node<ST>* x, vector<node<ST>*> V)
  {
    bool answer = false;
    int i = V.size()-1;
    while (i>=0 && !answer) 
      {
	if (x==V[i]) answer = true;
	i--;
      }
    return answer;
  }

  static bool checktreestruct(node<ST> *A)
  {
    // interior and frontier nodes:
    if (A==NULL) return true;
    bool answer = true;
    vector<node<ST>*> interior;
    vector<node<ST>*> frontier;
    frontier.push_back(A);
    node<ST> *current;
    while (frontier.size() > 0 && answer)
      {
	// pop frontier node, move to interior.
	current = frontier.back();
	interior.push_back(current);
	frontier.pop_back();
        // checking if children of current node already exists.
	if (memb(current->left,frontier) 
	    || memb(current->left,interior)
	    || memb(current->right,frontier) 
	    || memb(current->right,interior)
	    || (current->left==current->right && current->left!=NULL))
	  { answer = false; }
	else  // add nodes to frontier, as long as they're not null
	  {
	    if (current->left!=NULL) frontier.push_back(current->left);
	    if (current->right!=NULL) frontier.push_back(current->right);
	  }
      } // while frontier not empty
    return answer;
  } // checktree

  // The time complexity of this program is O(n*n) , since
  // each time through the loop we take one node off the frontier list,
  // at most the loop will run n times if n is the total number of nodes.
  // However, during each iteration of the loop, we have to check if two
  // nodes are already inside the frontier/interior list.  The lengths of
  // these lists are proportional to n (they can be as large as n-1 in the
  // worst case, and the "memb" operation is thus O(n).  In other
  // words, the recurrence relation here is T(n)=T(n-1)+C*n for some C.