LeetCode Entry

951. Flip Equivalent Binary Trees

24.10.2024 medium 2024 kotlin rust

Are trees flip-equal

951. Flip Equivalent Binary Trees medium blog post substack youtube deep-dive 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/778

Problem TLDR

Are trees flip-equal #medium #recursion #dfs

Intuition

The problem size is small, 100 elements, we can do a full Depth-First Search and emulate swaps

Approach

  • this problem is a one-liner recursion golf

Complexity

  • Time complexity: \(O(n^2)\), d = log(n) recursion depth, each time we try at most 4 searches, so it is 4^d = 4^log(n), simplified with identity of \(a^{\log(c)} = c^{\log(a)}\) to \(4^{log(n)} = n^{log(4)} = n^{2log_2(2)} = n^2\)

  • Space complexity: \(O(log(n))\)

Code


    fun flipEquiv(root1: TreeNode?, root2: TreeNode?): Boolean =
      root1?.run {
        `val` == (root2?.`val` ?: -1) && (
        flipEquiv(left, root2!!.left) &&
        flipEquiv(right, root2.right) ||
        flipEquiv(left, root2.right) &&
        flipEquiv(right, root2.left)) } ?: (root2 == null)



    pub fn flip_equiv(root1: Option<Rc<RefCell<TreeNode>>>,
                      root2: Option<Rc<RefCell<TreeNode>>>) -> bool {
        let Some(r1) = root1 else { return root2.is_none() };
        let Some(r2) = root2 else { return false };
        let (r1, r2) = (r1.borrow(), r2.borrow());
        r1.val == r2.val && (
            Self::flip_equiv(r1.left.clone(), r2.left.clone()) &&
            Self::flip_equiv(r1.right.clone(), r2.right.clone()) ||
            Self::flip_equiv(r1.left.clone(), r2.right.clone()) &&
            Self::flip_equiv(r1.right.clone(), r2.left.clone()))
    }



    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        return !root1 == !root2 && (!root1 || root1->val == root2->val && (
            flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right) ||
            flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left)));
    }