let's understand Iterative DFS, the interview material, with Added YouTube solution
Youtube Solution :- https://youtu.be/uM72t3y2uo4\n# Intuition && Approach\nwe will solve this using iterative DFS \n\nintuition is simple, we will start from th
# Youtube Solution :- https://youtu.be/uM72t3y2uo4\n# Intuition && Approach\nwe will solve this using iterative DFS \n\nintuition is simple, we will start from the root of both Tree:- \n\n**step1 :-** we will have a method **areEqulVal** that checks only the values of two nodes n1, and n2 passed to it, return true if same else false.\n\n**step2 :-** now in our main method we will create a Stack of **TreeNode array**, its array of size two as we will push pair from tree1 and tree2 nodes to the stack. initially pushed **root1** and **root2** as an array to the stack.\n\n**step3:-** now its time to pop out the values form stack, there could be below cases:- \n\nTreeNode[] temp = st.pop()==> **TreeNode n1 = temp[0], n2 = temp[1]**\n\n**1)** if left child and right child of both n1 and n2 are same\n  ==> areEqualVal(n1.left, n2.left) && areEqualVal(n1.right, n2.right)\n  ===> means we have to look further deeper, as left , right are same\n  ==> we will push **n1.left, n2.left** pair and **n1.right, n2.right** pair\n\n**2)** else if **n1.left , n2.right are same**\n        and **n1.right, n2.left are same**\n\n===> means flip operation can happen ===> we will push the pairs again for deeper checks\n===> will push the pair **(n1.left, n2.right)** and **(n1.right, n2.left)**\n\n**3)** else we have to **return false** because there is a mismatch which even can not make equal by any flip operation.\n\nwe will come out of while loop if they are flip equivalent so **return true**\n\n**for more details will release a youtube video no problem**\n\n\n# Code\n```java []\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public boolean areEqualVal(TreeNode n1, TreeNode n2)\n    {\n        if(n1==null && n2==null)\n        return true;\n        else if(n1!=null && n2!=null && n1.val == n2.val)\n        return true;\n        else\n        return false;\n    }\n    \n\n    public boolean flipEquiv(TreeNode root1, TreeNode root2) {\n    Stack<TreeNode[]>st = new Stack<>();\n    st.push(new TreeNode[]{root1, root2});\n\n    while(!st.isEmpty())\n    {\n      TreeNode[] temp = st.pop();\n      TreeNode n1 = temp[0], n2 = temp[1];\n      if(n1==null & n2==null)\n      continue;\n      if(n1==null || n2==null) return false;\n      if(n1.val!=n2.val) return false;\n\n      if( areEqualVal(n1.left, n2.left) &&  areEqualVal(n1.right,n2.right))\n      {\n        st.push(new TreeNode[]{n1.left, n2.left});\n        st.push(new TreeNode[]{n1.right, n2.right});\n      }\n      else if(areEqualVal(n1.left, n2.right) && areEqualVal(n1.right, n2.left))\n      {\n        st.push(new TreeNode[]{n1.left, n2.right});\n        st.push(new TreeNode[]{n1.right, n2.left});\n      }\n\n      else\n      return false;\n    }\n\n    return true;\n\n    }\n}\n```\n```C++ []\n\n\nclass Solution {\npublic:\n    bool areEqualVal(TreeNode* n1, TreeNode* n2) {\n        if (n1 == nullptr && n2 == nullptr)\n            return true;\n        else if (n1 != nullptr && n2 != nullptr && n1->val == n2->val)\n            return true;\n        else\n            return false;\n    }\n\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        stack<pair<TreeNode*, TreeNode*>> st;\n        st.push({root1, root2});\n\n        while (!st.empty()) {\n            auto temp = st.top();\n            st.pop();\n            TreeNode* n1 = temp.first;\n            TreeNode* n2 = temp.second;\n            if (n1 == nullptr && n2 == nullptr)\n                continue;\n            if (n1 == nullptr || n2 == nullptr || n1->val != n2->val)\n                return false;\n\n            if (areEqualVal(n1->left, n2->left) && areEqualVal(n1->right, n2->right)) {\n                st.push({n1->left, n2->left});\n                st.push({n1->right, n2->right});\n            } else if (areEqualVal(n1->left, n2->right) && areEqualVal(n1->right, n2->left)) {\n                st.push({n1->left, n2->right});\n                st.push({n1->right, n2->left});\n            } else {\n                return false;\n            }\n        }\n\n        return true;\n    }\n};\n\n```\n```python []\nprint(\'Hello world!\')\n```\n
['Math', 'Stack', 'Tree', 'Depth-First Search', 'Binary Tree', 'C++', 'Java']