Check two binary search trees have the same in-order traversal

Question

Check two binary search trees have the same in-order traversal. My naive approach is to in-order traverse the given two trees and copy each element onto an array separately, then check these two arrays are the same. But I feel like we should be able to just copy elements from one tree onto an array and use that array to verify the other tree on the fly, instead of using two arrays. Or better yet, there may be a way to do it without using any array. My code is following, not sure if my implementation of hasSameInOrder() is correct. Or could we do it without using any array? Please note that two trees having the same in-order traversal mean if you copy the elements onto an array when in-order traversing, the two resulted array should have the same value. So they don't necessarily have the same structure in order to have the same in-order traversal.

public boolean checkTwoBSTHaveSameInOrder(Node n1, Node n2) {
   LinkedList<Node> queue = new LinkedList<Node>();
   inOrder(n1, buffer);
   hasSameInOrder(n2, queue)
   return queue==null? false: true;
}
public void inOrder(Node node, LinkedList<Node> queue) {
   if (node==null)
       return;
   inOrder(node.left, queue);
   queue.add(node);
   inOrder(node.right, queue);
}
public void hasSameInOrder(Node node, LinkedList<Node> queue) {
   if (node==null)
      return;
   hasSameInOrder(n2.left, queue));
   if (queue==null)
      return;
   else {
      if (node!=queue.poll())
           queue=null;
   }
   hasSameInOrder(n2.right, queue));
} 

Answer 1

We can do it in more better space complexity O(1) We can use Morris Traversal to iterate over the trees and compare the values element by element.

I am assuming both tree have same number of nodes for the below implementation.

  bool isSame(root1, root2){
    while(root1!=null && root2!=null){
        while(root1->left!=NULL){
            auto maxleft = getmaxnode(root1->left);
            maxleft->right = root1;
            auto next = root1->left;
            root1->left = NULL;
            root1 = next;
        }
        while(root2->left!=NULL){
            auto maxleft = getmaxnode(root2->left);
            maxleft->right = root2;
            auto next = root2->left;
            root2->left = NULL;
            root2 = next;
        }
        if(root1->val != root2->val) return false;
    }
    return true;
}

Answer 2

There are two tree which in order are same as follow

1. InOrder function tree1 will populate queue
2. CheckInOrder function will compare the value with second tree
3. if there is a mismatch return false

    /*
      Tree 1           Tree 2
         5                3
        / \              / \
       3   7            1   6
      /   /                / \
     1   6                5   7
    [1,3,5,6,7]      [1,3,5,6,7]
    */
    
    #include <iostream>
    #include <queue>
    
    using namespace std;
    
    struct NODE {
        NODE() {
            val = 0;
            left = NULL;
            right = NULL;
        }
    
        NODE(int n) {
            val = n;
            left = NULL;
            right = NULL;
        }
        int val;
        NODE* left;
        NODE* right;
    };
    
    void InOrder(NODE* root, queue<int>& q)
    {
        if (root == NULL)
            return;

        InOrder(root->left, q);
        q.push(root->val);
        InOrder(root->right, q);
    }
        
    bool CheckInOrder(NODE* root, queue<int>& q)
    {
        if (root == NULL)
            return true;
        if (!CheckInOrder(root->left, q))
            return false;
        if (!q.empty() && root->val == q.front())
            q.pop();
        else
            return false;
    
        return CheckInOrder(root->right, q);
    }
    
    int main()
    {
        NODE* tree1;
        NODE* tree2;
        queue<int> tq;
    
        tree1 = new NODE(5);
        tree1->left = new NODE(3);
        tree1->right = new NODE(7);
        tree1->left->left = new NODE(1);
        tree1->right->left = new NODE(6);
    
        tree2 = new NODE(3);
        tree2->left = new NODE(1);
        tree2->right = new NODE(6);
        tree2->right->left = new NODE(5);
        tree2->right->right = new NODE(7);
    
        InOrder(tree1, tq);
        if (CheckInOrder(tree2, tq) && tq.empty())
            cout << "TRUE";
        else
            cout << "FALSE";
    }