Crack leetcode 101: Symmetric Tree

There is a way to make it easy.

Sometimes they make it look hard, while in fact, there’s always a way you can easily understand. Today, we’ll crack leetcode 101 — Symmetric Tree — together. Without further ado, let’s get started.

Problem description:

(photo taken from leetcode: https://leetcode.com/problems/symmetric-tree/)

Solution #1: Recursion:

Idea explaination:

I have to admit, as intuitive as it seems, it’s not the first thought for me. Now if I look back, there are things get me stuck in the first try, that I can share with you if you were in the same shoe.

First, by looking at the Example 1, I immediately noticed a leftSubTree and a rightSubTree, and they should mirror each other.

But then how to keep the recursion going?

This is where I get stuck, and now I realized all I need is to draw a higher tree:

And now I can see, to know if leftSubTree is mirror of rightSubTree, we need to get the following answers: if leftNode2.leftSubTree is mirror of rightNode2.rightSubTree, and if leftNode2.rightSubTree is mirror of rightNode2.leftSubTree, like what’s shown here:

Just like that, we would keep ask the same two questions, and the recursion goes on.

For example, when we are comparing if leftNode2.leftSubTree is mirror of rightNode2.rightSubTree, we compare the (leftSubTree on left) with the (rightSubTree on right), then (rightSubTree on left) with (leftSubTree on right).

This is when recursion became natural to me.

Python code:

Time and Space Complexity Analysis:

Worst-Case Time Complexity:

In the worst case, we need to check all the nodes in the tree. Therefore, the worst-case time complexity is O(N), where N is how many nodes there are in the tree.

Space Complexity:

First let’s work on the auxiliary space complexity. It’s main contributor is the recursion call-stack. How many recursive calls we need to make? In the worst case, the tree is symmetric in a way that it’s leftsubtree and rightsubtree both are linear. Therefore, auxiliary space consumption is N/2, or O(N).

And the input space is N. Therefore, the space complexity is O(N).

To Be Continued

We plan to explain solution #2: BFS in another time. So stay tuned!

The END

Thanks for reading! Please check our articles more often, if you’d like to support our work — and we’ll see you in the next one!