# 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:

# 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!