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 CodeFights 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 CodeFights Explainer article about trees.)

## 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 3 4 5 6 7 8 |
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 3 4 5 6 7 8 |
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:

1 2 3 4 5 6 7 |
# 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 |
1 / \ 2 3 / \ / \ 4 5 6 7 / 8 |

The subtree under node `2`

is:

1 2 3 4 5 6 |
2 / \ 4 5 / 8 |

While the subtree under node `6`

is:

1 2 3 4 |
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:

1 2 3 4 5 6 |
tree1 = A1 / \ B1 C1 / \ / \ .. .. .. .. |

with a similar structure for `tree2`

. We can think of `tree1`

as:

1 2 3 4 |
tree1 = A1 / \ {subtree L1} {subtree R1} |

`tree1`

and `tree2`

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

`A1`

and`A2`

are equal;- The tree
`{subtree L1}`

is equal to the`{subtree L2}`

(determined by calling`areTreesEqual(tree1.left, tree2.left)`

); - 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`

:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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`

.

1 2 3 4 5 6 |
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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
# 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 CodeFights, 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:

1 2 3 4 5 6 7 8 9 10 11 12 |
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 CodeFights 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?

1 2 3 4 5 6 7 8 9 10 11 12 13 |
# 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
# 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!