✨ Solution - Recursive depth-first traversal in Typescript 💯🚀✔
Intuition\nTwo binary trees are considered flip equivalent if one can be transformed into the other through a series of flip operations. A flip operation involv
# Intuition\nTwo binary trees are considered flip equivalent if one can be transformed into the other through a series of flip operations. A flip operation involves swapping the left and right child subtrees of any node in the tree. To determine if two trees are flip equivalent, we need to recursively compare their structures and values, taking into account the possibility of flipping.\n\n# Approach\n1. **Base Cases**:\n   - If both trees are `null`, they are considered equivalent.\n   - If one tree is `null` and the other is not, they are not equivalent.\n   - If the values of the current nodes in both trees do not match, they are not equivalent.\n\n2. **Recursive Comparison**:\n   - For the current nodes, we have two scenarios to consider:\n     - **Without Flipping**: Compare the left child of tree1 with the left child of tree2 and the right child of tree1 with the right child of tree2.\n     - **With Flipping**: Compare the left child of tree1 with the right child of tree2 and the right child of tree1 with the left child of tree2.\n   - The trees are equivalent if either of the two scenarios returns true.\n\n# Complexity\n- **Time Complexity**: ***O(n)***, where n is the number of nodes in the trees. We traverse each node once.\n- **Space Complexity**: ***O(h)***, where h is the height of the tree, due to the recursion stack.\n\n# Code\n\n```typescript\nclass TreeNode {\n    val: number;\n    left: TreeNode | null;\n    right: TreeNode | null;\n    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {\n        this.val = (val === undefined ? 0 : val);\n        this.left = (left === undefined ? null : left);\n        this.right = (right === undefined ? null : right);\n    }\n}\n\nfunction flipEquiv(root1: TreeNode | null, root2: TreeNode | null): boolean {    \n    if (!root1 && !root2) return true;\n    if (!root1 || !root2) return false;\n    if (root1.val !== root2.val) return false;\n\n    return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||\n           (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));\n};\n\n```\n## Example usage\n\n```typescript\nconst root1 = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6)));\nconst root2 = new TreeNode(1, new TreeNode(3, null, new TreeNode(6)), new TreeNode(2, new TreeNode(4), new TreeNode(5)));\nconsole.log(flipEquiv(root1, root2)); // Output: true\n```\n\n### Explanation and Example Walkthrough\n\n#### Example 1\n**Input**:\n- `root1 = [1,2,3,4,5,6,null,null,null,7,8]`\n- `root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]`\n\n1. Starting with the root node (1 in both trees):\n   - Both have the same value, proceed to check children.\n   \n2. Check children without flipping:\n   - Left child of `root1` (2) with left child of `root2` (3) \u2192 Not equivalent.\n   \n3. Check children with flipping:\n   - Left child of `root1` (2) with right child of `root2` (2) \u2192 Values match.\n   - Right child of `root1` (3) with left child of `root2` (3) \u2192 Check equivalence.\n\nContinuing recursively down both paths confirms the trees are flip equivalent, returning true.\n\n#### Example 2\n**Input**:\n- `root1 = []` (null)\n- `root2 = []` (null)\n\nBoth trees are empty, so they are trivially equivalent. The output is true.\n\n#### Example 3\n**Input**:\n- `root1 = []` (null)\n- `root2 = [1]` (a single node)\n\nHere, `root1` is null while `root2` is not, so they cannot be equivalent. The output is false.\n\nThis approach effectively uses recursive depth-first traversal to explore the binary trees, checking for flip equivalence at each node.
['TypeScript']