CLEAN CODE: SYMMETRIC BINARY TREE

By: Saurav

2018-01-19 10:42:00 UTC

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Example :

1
/ \
2 2
/ \ / \
3 4 4 3
The above binary tree is symmetric.
But the following is not:

1
/ \
2 2
\ \
3 3
Return 0 / 1 ( 0 for false, 1 for true ) for this problem

InterviewBit

This problem is actually simpler if you think out of the box. In the start, I started with comparing mirror elements in one tree itself and it became too complex due to null checks.

The best strategy:

Take two copies of the same tree and run a recursive function which compares left subtree with right one and vice versa if the two node's data are equal.

Let's see in action:

def isSymmetric(a)
        return 1 if !a
        symmetric_trees(a,a) ? 1 : 0
    end
    
    def symmetric_trees(a,b)
        
        return true if !a and !b
        
        if a and b and a.data == b.data
           return (symmetric_trees(a.left,b.right) and symmetric_trees(a.right,b.left))
        end
        
        return false
        
    end

Looks good to me.


Let me know what you think!
twitter: sprakash24oct
linkedin

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)