Symmetric Tree - Leetcode 101 - Python

NeetCodeIO · Beginner ·⚡ Algorithms & Data Structures ·3y ago

Key Takeaways

The video demonstrates a solution to the Symmetric Tree problem on LeetCode using a recursive Depth-First Search (DFS) approach in Python, checking if a binary tree is a mirror of itself by comparing the left and right subtrees.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem symmetric tree we're given the root of a binary tree and we just want to check if it's a mirror of itself so what that really means is we're just comparing the left subtree of the root and the right subtree of the root the root itself doesn't really matter because think about it a node is pretty much symmetric with itself so then analyzing the subtrees for them to be symmetric well the roots have to be equal so we have to check are the root values equal in this case yes they are 2 is equal to 2. now this is where things get different from leak code 100 which is the same tree problem I believe where we're just comparing the two trees and checking if they're equal and this time we're doing it slightly differently we're not checking if the left child of 2 is equal we're not checking if these two nodes are equal we're checking if the left child of 2 is equal to the right child of 2 on on this side we're looking at them on opposite sides and similarly we're going to compare the inner Childs as well so here the right child here the left child are they the same and this is a pretty small tree so we don't know for sure if the way I'm kind of explaining it right now is going to work for the entire tree so let's draw a bigger one so this tree is similar to this one but we've added another layer so let's see recursively if our previous algorithm will still work so starting at three what are we going to do we're gonna compare opposite children so we're going to compare the right child of this guy and the left child of this guy and yeah that is going to work in this case because yes these two sub trees are symmetrical so you we can see that this algorithm is recursive in nature just like the tree so our algorithm is going to hold and looking at the left child here it's null and looking at the right child over here it's also null so that's going to be our base case case so for a tree to be symmetric eventually we're going to have to reach null nodes and null nodes will say are symmetric so I didn't draw all of these but we're going to assume that there are null children for each of these now going back to four we know that these themselves are opposite nodes we knew that earlier but now running our symmetric recursive algorithm on this sub tree we're going to check the left child of this four with the right child of this four they're the same and the right child of this four with the left child of this four they're the same so we can see yeah the algorithm is going to hold its recursive in nature we're going to have to pretty much run a DFS on the left subtree and a DFS on the right subtree at the same time simultaneously to compare nodes in both trees which means we're going to visit every single node in the entire tree so it's going to be an O of n algorithm where n is the number of nodes and the memory complexity is going to be the height of the tree just like with any DFS algorithm so now let's code it up so like I said we want to run this recursively so I'm going to Define an inner function which I'm going to call DFS you don't necessarily need to make this an inner function but you do need to Define another function because we're going to need to pass in two parameters which are going to be the roots of each of the sub trees left and right because our outer function only takes a single parameter so we need both parameters and with DFS you always want to start with a base case what's going to be the base case well what if both of the nodes are null so if not left and not right so both nodes are null what does that mean well basically the tree is symmetrical if both of them don't have a node in that position so we're going to return true in that case now what if only one of the nodes is null and the other one is not first of all how do we know that well if we get to this point we know that both of the nodes can't possibly be null so we're going to check if one of the nodes is null I do we do that well if not left or not right we know that one of the nodes is not null in that case we have to return false because the trees are definitely not symmetrical we want to compare these two nodes left and right if one of them is null and the other one isn't we can't compare them so we have to immediately return false now if neither of these is true that means both of the nodes are going to be non-null by definition because if one of them wasn't all we would have returned so now we can finally compare the nodes we want to compare the values of the left node and the value of the right node we can do that just like this they have to be equal for us to be able to return true from this DFS but not only do these nodes have to be equal we have to compare the sub trees how are we going to do that we're going to call DFS on the left node and it's left subtree and we're going to compare that subtree with the right subtree from the right node because they are opposites and then we also want to compare the inner nodes or the inner subtrees so we're going to call DFS on left dot right and we're going to compare that with right dot left I know it's a bit confusing because the sub trees are called left and right and the trees themselves that we named are left and right as well but I hope that this is clear we're clearly comparing the Opposites left with right and right with left so this will evaluate to a Boolean and not only that these two recursive functions won't execute if this evaluates to false because if this is false since these are chained with an and operator this whole thing will be false if this is false that means we won't end up executing any unnecessary work so what I'm going to do with this is turn it into a Boolean or well it's already a Boolean but I'm just going to wrap it in parentheses and then return the entire value and before we try to submit our code make sure to actually call the DFS that's a step I usually forget so calling DFS on root dot left and root dot right so now let's run the code to make sure that it works okay my brain is lagging a bit we have an extra and operator I don't know how that got there sorry about that but as you can see it works and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neetcode.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon

Original Description

🚀 https://neetcode.io/ - Get lifetime access to every course I ever create! Solving Leetcode 101 - Symmetric Tree, today's daily leetcode problem on March 12th. 🥷 Discord: https://discord.gg/ddjKRXPqtk 🐦 Twitter: https://twitter.com/neetcode1 📷 Instagram: https://www.instagram.com/neetcodeio/ 🎵 TikTok: https://www.tiktok.com/@neetcode.io 🐮 Support the channel: https://www.patreon.com/NEETcode ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf 💡 DYNAMIC PROGRAMMING PLAYLIST: https://www.youtube.com/watch?v=73r3KWiEvyk&list=PLot-Xpze53lcvx_tjrr_m2lgD2NsRHlNO&index=1 Problem Link: https://leetcode.com/problems/symmetric-tree/ 0:00 - Read the problem 0:30 - Drawing Explanation 2:55 - Coding Explanation leetcode 101 #leetcode #neetcode #python
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 49 of 60

← Previous Next →
1 Leetcode 149 - Maximum Points on a Line - Python
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
 2 Design Linked List - Leetcode 707 - Python
Design Linked List - Leetcode 707 - Python
NeetCodeIO
 3 Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
 4 Design Browser History - Leetcode 1472 - Python
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
 5 Number of Good Paths - Leetcode 2421 - Python
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
 6 Flip String to Monotone Increasing - Leetcode 926 - Python
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
 7 Maximum Sum Circular Subarray - Leetcode 918 - Python
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
 8 Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
 9 Concatenated Words - Leetcode 472 - Python
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
 10 Data Stream as Disjoint Intervals - Leetcode 352 - Python
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
 11 LFU Cache - Leetcode 460 - Python
LFU Cache - Leetcode 460 - Python
NeetCodeIO
 12 N-th Tribonacci Number - Leetcode 1137
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
 13 Best Team with no Conflicts - Leetcode 1626 - Python
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
 14 Greatest Common Divisor of Strings - Leetcode 1071 - Python
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
 15 Shortest Path in a Binary Matrix - Leetcode 1091 - Python
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
 16 Insert into a Binary Search Tree - Leetcode 701 - Python
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
 17 Delete Node in a BST - Leetcode 450 - Python
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
 18 Shuffle the Array (Constant Space) - Leetcode 1470 - Python
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
 19 Fruits into Basket - Leetcode 904 - Python
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
 20 Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
 21 Naming a Company - Leetcode 2306 - Python
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
 22 As Far from Land as Possible - Leetcode 1162 - Python
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
 23 Shortest Path with Alternating Colors - Leetcode 1129 - Python
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
 24 Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
 25 Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
 26 Contains Duplicate II - Leetcode 219 - Python
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
 27 Path with Maximum Probability - Leetcode 1514 - Python
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
 28 Add to Array-Form of Integer - Leetcode 989 - Python
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
 29 Unique Paths II - Leetcode 63 - Python
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
 30 Minimum Distance between BST Nodes - Leetcode 783 - Python
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
 31 Design Hashmap - Leetcode 706 - Python
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
 32 Range Sum Query Immutable - Leetcode 303 - Python
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
 33 Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
 34 Middle of the Linked List - Leetcode 876 - Python
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
 35 Course Schedule IV - Leetcode 1462 - Python
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
 36 Single Element in a Sorted Array - Leetcode 540 - Python
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
 37 Capacity to Ship Packages - Leetcode 1011 - Python
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
 38 IPO - Leetcode 502 - Python
IPO - Leetcode 502 - Python
NeetCodeIO
 39 Minimize Deviation in Array - Leetcode 1675 - Python
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
 40 Longest Turbulent Array - Leetcode 978 - Python
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
 41 Last Stone Weight II - Leetcode 1049 - Python
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
 42 Construct Quad Tree - Leetcode 427 - Python
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
 43 Find Duplicate Subtrees - Leetcode 652 - Python
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
 44 Sort an Array - Leetcode 912 - Python
Sort an Array - Leetcode 912 - Python
NeetCodeIO
 45 Ones and Zeroes - Leetcode 474 - Python
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
 46 Remove Duplicates from Sorted Array II - Leetcode 80 - Python
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
 47 Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
 48 Concatenation of Array - Leetcode 1929 - Python
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
 ▶ Symmetric Tree - Leetcode 101 - Python
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
 50 Check Completeness of a Binary Tree - Leetcode 958 - Python
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
 51 Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
 52 Find Peak Element - Leetcode 162 - Python
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
 53 Accounts Merge - Leetcode 721 - Python
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
 54 Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
 55 Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
 56 Number of Zero-Filled Subarrays - Leetcode 2348 - Python
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
 57 Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
 58 Sqrt(x) - Leetcode 69 - Python
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
 59 Successful Pairs of Spells and Potions - Leetcode 2300 - Python
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
 60 Optimal Partition of String - Leetcode 2405 - Python
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO

This video teaches how to solve the Symmetric Tree problem on LeetCode using a recursive DFS approach in Python, covering algorithm design, binary trees, and recursion. The solution checks if a binary tree is symmetric by comparing its left and right subtrees.

Key Takeaways
  1. Define the problem and understand the concept of a symmetric tree
  2. Design a recursive DFS algorithm to compare the left and right subtrees
  3. Implement the algorithm in Python, handling base cases and recursive calls
  4. Analyze the time and space complexity of the algorithm
  5. Test the solution with example inputs
💡 The key insight is to use a recursive DFS approach to compare the left and right subtrees of the binary tree, checking if they are mirrors of each other.

Related AI Lessons

⚡
Bloom Filters, Explained Properly
Learn how Bloom filters work and their benefits, including tiny memory and blazing speed, in exchange for potential false positives.
Dev.to · Daksh Gargas
 ⚡
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Learn how prefix sums enable instant range queries in arrays, boosting performance in various applications
Medium · Programming
 ⚡
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
A simple math question can destroy a developer's interview, highlighting the importance of being prepared for unexpected questions
Medium · Programming
 ⚡
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Learn to remove duplicates from a sorted array using the two pointers technique, improving from brute force to optimized solutions
Medium · Python

Chapters (3)

Read the problem
0:30 Drawing Explanation
2:55 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →