# Tweaked Binary tree

Determine whether two given binary trees are identical assuming any number of ‘tweak’s are allowed. A tweak is defined as a swap of the children of one node in the tree.

**Examples**

        5

      /    \\

    3        8

  /   \\

1      4

and

        5

      /    \\

    8        3

           /   \\

          1     4

the two binary trees are tweaked identical.

**How is the binary tree represented?**

We use the level order traversal sequence with a special symbol "#" denoting the null node.

**Solution:** Recursive bottom up check

**Base Case:** 

1. if n1 and n2 == null return true
2. n1 or n2 == null return false
3. n1.value != n2.value return false

**Recursive Rule:**

1. Call self on (left.left , right.right) && (left.right, right.left) || (left.left, right.left) && (left.right, right.right)

**Implementation:**

 

```
public boolean tweakedSymTree(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    else if (left == null || right == null) return false;
    else if (left.value != right.value) return false;
    
    return tweakedSymTree(left.left, right.right) && tweakedSymTree(left.right, right.left)
    || tweakedSymTree(left.left, right.left) && tweakedSymTree(left.right, right.right);
    
    }
```

**Time Comp:** O(Every Node in Recursive Tree) = O(Splits per layer ^ layers) 

Recursive Tree splits four way unlike input tree, therefore Splits per layer = 4

Layers in binary tree = log2(N)

Total TC = 4^log2(N) = 2^2log2(N) = 2^log2(N^2) = **N^2**

**Space Comp:** O(Each Node four calls) = **O(4^N)**