/*
  tree_compare.cpp

  Written 2000 by Keunwoo Lee (klee@cs)

  Demonstrates how to compare the elements of two trees in O(n) time
  using O(h) space, where n is the number of nodes in both trees and h
  is the height of the deeper tree.  With reasonably balanced trees,
  this will be O(nlogn) space.

  Fairly tricky.  Reader beware...

  Of course, this is far beyond what we would have expected students
  to implement on the final.  Much easier algorithms that use either

     - O(n) time and O(n) space, or
     - O(nlogn) time and O(logn) space

  exist, and those are what we expected students to write.  This
  example is provided as a bit of fun for students who might be
  interested in a solution that combines the best of both solutions'
  asymptotic costs, at the cost of some extra trickiness in the
  algorithm.

 */

#include <cassert>
#include <cstdlib>
#include <iostream>
using namespace std;

struct Node {
    double value;
    Node *left, *right;

    // Convenience constructors (don't be frightened by the default
    // arguments or initializer list syntax in the second one).
    Node() : left(NULL), right(NULL) {}
    Node(double init_value, Node *init_left = NULL, Node *init_right = NULL)
        : value(init_value), left(init_left), right(init_right) {}
};

typedef Node* Node_ptr;

// PROTOTYPES
void insert(Node *& node, double toInsert);
void print_inorder(Node * node);
int max(int x, int y);
int max_depth(Node *node);
bool isContentEqual(Node *a, Node *b);
bool contentEqualHelper(Node *a_stack[], Node *b_stack[], int& a_depth, int& b_depth);

//////////////////////////////////////////////////////////////////////
// MAIN

// This driver tests the isContentEqual implementation by running a
// series of insertions, followed by tests.  If the function works
// properly, it should print "equal" (ITEMS_PER_RUN + 2) times,
// followed by "not equal" (ITEMS_PER_RUN * 2) times.
int main()
{
    const int ITEMS_PER_RUN = 7;  // Number of items per test run
    Node *x = NULL, *y = NULL;    // Two empty trees
    int i; // Workaround for MSVC++'s improper for loop scoping.

    // Seed the random number generator.  Use a different seed to try
    // different values.
    srand(1238);

    // Test the empty case.  Should be equal.
    cout << (isContentEqual(x, y) ? "equal" : "not equal") << endl;

    // Test the equal case
    for (i=0; i<ITEMS_PER_RUN; i++) {
        int rand_val = rand();
        insert(x, (double)rand_val);
        insert(y, (double)rand_val);
        cout << (isContentEqual(x, y) ? "equal" : "not equal") << endl;
    }

    // Test the different-shaped equal case.  Should be equal.
    insert(x, 9.0);    // Add to x
    insert(x, 14.0);
    insert(x, 12.0);
    insert(x, 17.0);
    insert(x, 4.0);
    insert(x, -23.0);
    insert(y, 12.0);   // Add same values to y, in different order
    insert(y, 4.0);
    insert(y, -23.0);
    insert(y, 9.0);
    insert(y, 17.0);
    insert(y, 14.0);
    cout << (isContentEqual(x, y) ? "equal" : "not equal") << endl;
    

    // Test the unequal case---extremely improbable that there should
    // ever be equality from 2 randomly selected values.  Should be
    // not equal.
    for (i=0; i<ITEMS_PER_RUN; i++) {
        insert(x, (double)rand());
        insert(y, (double)rand());
        cout << (isContentEqual(x, y) ? "equal" : "not equal") << endl;
    }

    // Test the different-height case.  Should be not equal.
    for (i=0; i<ITEMS_PER_RUN; i++) {
        insert(x, (double)rand());
        cout << (isContentEqual(x, y) ? "equal" : "not equal") << endl;
    }

    return 0;
}

//////////////////////////////////////////////////////////////////////
// THE REAL DEAL

//
// The major idea is that you iterate in order through all the nodes
// in both tree A and tree B.
//
// We use a stack to keep track of the nodes that are in the current
// node's parent chain, so that you can crawl back up to higher levels
// of the tree when you are done iterating through a subtree of A or a
// subtree of B.
//
// The implementation is, shall we say, subtle.
//
bool isContentEqual(Node *a, Node *b)
{
    int a_depth = max_depth(a);
    int b_depth = max_depth(b);

    // Handle empty tree case, whether both empty or only one.
    // Strictly speaking, we don't need this; it's really an
    // optimization for the empty tree cases.
    assert(a_depth >= 0 && b_depth >= 0);
    if (a_depth == 0 && b_depth == 0) {
        return true;
    } else if (a_depth == 0 || b_depth == 0) {
        return false;
    }

    // We will stacks no deeper than the depth of the trees.
    Node_ptr *a_stack = new Node_ptr[a_depth];
    Node_ptr *b_stack = new Node_ptr[b_depth];

    // Prime a's stack by pushing everything on the path from the root
    // to the minimum value in the tree.
    int a_top = -1;
    Node *leftmost = a;
    while (leftmost != NULL) {
        a_stack[++a_top] = leftmost;
        leftmost = leftmost->left;
    }

    // Prime b's stack likewise.
    int b_top = -1;
    leftmost = b;
    while (leftmost != NULL) {
        b_stack[++b_top] = leftmost;
        leftmost = leftmost->left;
    }

    // Call the recursive helper function, which does the hard work.
    bool retval = contentEqualHelper(a_stack, b_stack, a_top, b_top);

    // Cleanup & return
    delete [] a_stack;
    delete [] b_stack;
    return retval;
}

//
// Once the stack been primed, this helper will repeatedly 
//
//    1. Pop the next element off both stacks,
//    2. Compare them for equality, and
//    3. Set the stacks so that they point to the next element in
//       sequence for both trees.
//
// If any difference in the sequences is found, of course we
// return false.
//
// The best way to understand this function is to picture the answer
// to the question: "If I have a node in a binary tree, how do I find
// this node's direct successor?"  Once you have that answer, the rest
// becomes clear, with some thought.
//
bool contentEqualHelper(Node *a_stack[], Node *b_stack[], int& a_top, int& b_top)
{
    if (a_top < 0 && b_top < 0) {
        return true;
    } else if (a_top < 0 || b_top < 0) {
        return false;
    } else {

        // Pop the stacks.  We maintain the invariant that no item
        // will be popped until every item in its left subtree has
        // been tested and found equal.
        assert(a_top >= 0 && b_top >= 0);
        Node * a_node = a_stack[a_top--];
        Node * b_node = b_stack[b_top--];

        if (a_node->value != b_node->value) {
            return false;
        } else {
            
            // We're ok.  Now, we set the stack for the next
            // iteration, which means making sure the next element is
            // at the top of the stack.
            //
            // The next element of each subtree is either the parent
            // node or the leftmost node in the right subtree.  The
            // parent node is already on the stack, so if the right
            // subtree is NULL.
            //
            // Otherwise, we push the leftmost node in the right
            // subtree, along with all of its parents.

            if (a_node->right != NULL) {
                Node * a_next = a_node->right;
                while (a_next != NULL) {
                    a_stack[++a_top] = a_next;
                    a_next = a_next->left;
                }
            }

            if (b_node->right != NULL) {
                Node * b_next = b_node->right;
                while (b_next != NULL) {
                    b_stack[++b_top] = b_next;
                    b_next = b_next->left;
                }
            }

            // Now, we can safely recurse.  I could make this iterative,
            // but recursion is clearer, and we're using O(height) space
            // anyway so who cares about the memory.
            return contentEqualHelper(a_stack, b_stack, a_top, b_top);
        }
    }
}

//////////////////////////////////////////////////////////////////////
// HELPER FUNCTIONS

// Precondition: if the tree is empty, node == NULL; otherwise,
//               node must point to a valid node.
void insert(Node *& node, double toInsert)
{
    if (node == NULL) {
        node = new Node(toInsert);
    } else {
        if (node->value > toInsert) {
            insert(node->left, toInsert);
        } else {
            insert(node->right, toInsert);
        }
    }
}

void print_inorder(Node *node)
{
    if (node != NULL) {
        print_inorder(node->left);
        cout << node->value << endl;
        print_inorder(node->right);
    }
}

int max(int x, int y)
{
    return (x > y ? x : y);
}

int max_depth(Node *node)
{
    if (node == NULL) {
        return 0;
    } else {
        int left_depth = max_depth(node->left);
        int right_depth = max_depth(node->right);
        return 1 + max(left_depth, right_depth);
    }
}