Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Two tree are the same if

1. Both root nodes are either both empty of both valid
2. The left subtree of p is the same as the left sub tree of q
3. The right subtree of p is the same as the right sub tree of q

So we can write a recursive code to check the above three conditions

    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL) return true;
        if(p != NULL and q == NULL or(p == NULL and q != NULL))return false;
        return (p->val == q->val && isSameTree(p -> left, q -> left) && isSameTree(p -> right, q -> right));
    }

ITerative

DFS

To use DFS, we want to first go as deep as possible, so we use a stack to enforce FILO policy so we will always go deep with the current node and only explore other branch when the current branch hit the bottom (null on both left and right children)

    bool isSameTree(TreeNode* p, TreeNode* q) {
        stack<TreeNode*> s;
        s.push(p);
        s.push(q);
        while(!s.empty()){
            TreeNode* leftNode = s.top();
            s.pop();
            TreeNode* rightNode = s.top();
            s.pop();
            if(leftNode == NULL && rightNode != NULL) return false;
            if(leftNode != NULL && rightNode == NULL) return false;
            if(leftNode != NULL && rightNode != NULL){
                if(leftNode -> val == rightNode -> val){
                    s.push(leftNode -> left);
                    s.push(rightNode -> left);
                    s.push(leftNode -> right);
                    s.push(rightNode -> right);
                }
                else{
                    return false;
                }
            }
        }
        return true;
    }