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)