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:

Image for post
Image for post
(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.

Image for post
Image for post

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:

Image for post
Image for post

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:

Image for post
Image for post

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

Image for post
Image for post

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:

Image for post
Image for post

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!

Written by

Life is beautiful!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store