CodeSignal Solves It: isTreeSymmetric

tree coding challenge interview question

The most recent Interview Practice Challenge of the Week was isTreeSymmetric. This interview question from LinkedIn and Microsoft is checking to see how comfortable you are with the tree data structure. Trees have a wide variety of applications, so your interviewer is going to make sure that you know your stuff!

Have you solved it yet? If not, head over to CodeSignal and give it a shot. Once you have a solution, come back here and I’ll walk you through how to answer this interview question. (Need to review first? Check out the CodeSignal Explainer article about trees.)

solve this tree challenge
This cat is definitely solving isTreeSymmetric right now. You should too!

The technical interview question

Done? Okay, let’s get started!

Our job is to determine if a (binary) tree is a mirror image of itself. That is, we want to know if the left side mirrors the right side. Here is an example of a symmetric tree:

    1
   / 
  2   2
 /  / 
3  4 4  3

(Symmetric tree: left-hand side mirrors the right-hand side)

In contrast, this is not a symmetric tree:

    1
   / 
  2   2
 /  / 
3  4 3  4

(Not a symmetric tree: left-hand side is equal to the right-hand side)

The tree on the bottom is the same on the left and the right. In other words, starting at each 2, you get exactly the same tree. But it’s not a mirror image because the left and right sides — the 3 and 4 — don’t swap positions.

We are going to implement a tree in Python with the following data structure:

# Definition for binary tree:
class Tree(object):
   def __init__(self, x):
     self.value = x
     self.left = None
     self.right = None     

Subtrees and recursion

A subtree is what we get by starting at any node, and treating it as the root of its own tree. For example, consider the tree:

      1
     / 
    2   3
   /  / 
  4  5 6  7
 /
8

The subtree under node 2 is:

    2
   / 
  4   5
 /
8

While the subtree under node 6 is:

    6

(You can see that it's just `6` by itself, without any children.)

A simpler question: Are left and right sides equal?

Let’s start with a slightly simpler problem. We’ll ask if the left-hand side of the tree is equal to the right-hand side of the tree, and we’ll assume that we have at least three nodes. With these assumptions, this is the same as asking whether the subtree under the first left node is the equal to the subtree under the first right node. Since subtrees are trees in their own right, what we would like is a function areTreesEqual(treeLeft, treeRight).

To figure out how to determine if two trees tree1 and tree2 are equal, we’ll turn to recursion. We have two trees, tree1 and tree2. Suppose that each tree has at the first two levels full (i.e. we have the root and both a left and right branch on level 1). Then tree1 looks like the following:

tree1 =   A1
        /   
       B1    C1
      /    / 
     .. .. .. ..

with a similar structure for tree2. We can think of tree1 as:

tree1 =    A1
          /  
{subtree L1} {subtree R1}

tree1 and tree2 are equal if and only if all of the following are true:

  1. A1 and A2 are equal;
  2. The tree {subtree L1} is equal to the {subtree L2} (determined by calling areTreesEqual(tree1.left, tree2.left));
  3. The tree {subtree R1} is equal to the {subtree R2} (determined by calling areTreesEqual(tree1.right, tree2.right)).

Now we need to work out the base case, so that the recursion will terminate. We assumed above that the first two levels would be full. This certainly isn’t true for leaf nodes, and even close to the root we may not have two branches. Here are the cases we need to consider that don’t fall into the recursion above:

  • Both trees are at a leaf (i.e. no children on either side). Just check to see if the values of the nodes are the same; if they are then these two subtrees are equal.
  • Either the left or right side is missing from both nodes. If the sides are the same, just check that side. If the sides are different (e.g. tree1 has no left side, but tree2 has no right side) then the trees are not equal.
  • The left side or right side is missing from only one node. Then the two trees are automatically not equal.

We now have enough information to write our function areTreesEqual:

def areTreesEqual(tree1, tree2):
    # Base cases:
    # if we are at a None (end of branch) for both trees, return True
    if tree1 == None and tree2 == None:
        return True
    # if only one is None, then it cannot equal the other one as not None
    if tree1 == None or tree2 == None:
        return False

    # check1: are the values of the root nodes the same?
    if tree1.value != tree2.value:
        return False

    # now the recursive step: these nodes are not equal if the LHS are different
    #                         if LHS same, then still have to check RHS
    if areTreesEqual(tree1.left, tree2.left) == False:
        return False

    # Since LHS are equal, tree1 and tree2 are equal if RHS is the same
    return areTreesEqual(tree1.right, tree2.right)

A function areBranchesEqual, which tests if the two branches of a tree are equal, could then be written to first check if we have a root node, then use areTreesEqual on the two subtrees root.left and root.right.

def areBranchesEqual(tree):
    # if there are no nodes, then return True (nothing on left, nothing on right)
    if tree == None:
        return True
    return areTreesEqual(tree.left, tree.right)

The original problem: isTreeSymmetric?

The big difference between isTreeSymmetric and areBranchesEqual is implementing the mirroring. When we investigate the left hand path of a node on one side, we have to investigate the right hand side on the other. Our full code is:

# Note the underscore: this function probably isn't generally useful
# outside of isTreeSymmetric
def _areTreesMirrorImages(t1,t2):
    # base cases
    if t1 == None and t2 == None:
        return True
    if t1 == None or t2 == None:
        return False
    if t1.value != t2.value:
        return False

    # compare the left side of t1 to the right side of t2
    if _areTreesMirrorImages(t1.left,t2.right) == False:
        return False

    # ... and compare the right side of t1 to the left side of t2
    return _areTreesMirrorImages(t1.right, t2.left)

def isTreeSymmetric(t):
    if t == None:
        return True
    return _areTreesMirrorImages(t.left,t.right)

The problem with recursion

So far we have a really neat and elegant solution for this interview question. It passes all of the tests on CodeSignal, including the hidden ones. A lot of tree problems lend themselves really well to being solved with recursion. However, in a technical interview, the interviewer might point out that the constraints of the problem told us that we were guaranteed the tree would be smaller than 5 * 10^4 values. Could we trigger a maximum recursion depth error in Python? (In other languages, the general term for this is “run out of stack space”).

Our algorithm is a depth-first search check, so if we run into problems it will be on very deep trees. Whenever we move down a level, before calling the recursive step we check if the current left side and right side are equal. So our worst case scenario tree would be:

worst_case =                                         1
                                                   /   
                                                  2     2
                                                 /       
                                                3         3
                                               /           
                                              4             4
                                             /              
                                            ...             ...
                                           /                 
                                         24999               24999

The depth of this tree is 24999, and the (default) maximum recursion depth in Python is only 1000. Thankfully CodeSignal didn’t give us this “torture test” for our algorithm! But how would we deal with it if our interviewer asked us to solve these trees?

# Constructing the worst case scenario
root = Tree(1)
root.left, root.right = Tree(2),Tree(2)
left, right = root.left, root.right
for i in range(3,25000):
    left.left   = Tree(i)
    right.right = Tree(i)
    left, right = left.left, right.right

# Test: will trigger max recursion depth -- this will fail with
# a RuntimeError
isTreeSymmetric(root)

The solution is to convert the recursive algorithm into an iterative one.

# this is the iterative version
def _areTreesMirrorImages(t1,t2):
    leftSide = [t1]
    rightSide =[t2]

    while leftSide and rightSide:
        currentLeft = leftSide.pop()
        currentRight = rightSide.pop()

        if currentLeft == None and currentRight == None:
            continue # nothing left to check for these two cases

        if currentLeft == None or currentRight == None:
            # one side has terminated -- don't match
            return False

        if currentLeft.value != currentRight.value:
            return False

        # Now to implement the "recursion" by using the two lists.
        # We want to compare currentLeft.left subtree with currentRight.right subtree
        # so have to add to leftSide and rightSide in that order
        leftSide.append(currentLeft.left)
        rightSide.append(currentRight.right)

        # Compare currentLeft.right subtree to currentRight.left subtree
        leftSide.append(currentLeft.right)
        rightSide.append(currentRight.left)

    # if we get to the end, we have exhausted at least one of left side or right side.
    # if we have exhausted both, we are done
    return len(leftSide) + len(rightSide) == 0

Phew! Though the recursion version is a lot easier to read, it’s a good idea to practice rewriting recursive algorithms as iterative ones since there are limitations on how many successive recursive calls you can make before returning.

Tell us…

How did you solve this Interview Practice challenge? Have you ever encountered it (or one like it!) in an interview? Let us know over on the forum!

Related Posts

Copyright © 2018 BrainFights Inc. All rights reserved.​