Leaf-Similar Trees - Leetcode 872 - Python
Key Takeaways
The video solves the Leaf-Similar Trees problem on LeetCode using a recursive Depth-First Search (DFS) approach in Python, comparing the leaf node sequences of two binary trees.
Full Transcript
hey everyone welcome back and let's write some more neat code today so today let's solve the problem Leaf similar trees we're given the root of two binary trees and we want to know if they are Leaf similar to each other which really just means if you take every leaf node which by the way a leaf node in a tree is just a node that doesn't have any children so of course every tree has to have some Leaf nodes because otherwise they would be like never ending it'd be like infinite or something so we take the sequence of leaf nodes in the first string and when we say sequence we mean from left to right so six 7 4 9 8 that's the sequence and we do the same thing for the right sub tree as well 6 7 4 9 8 and we want to know are these two sequences equal to each other in this case they are so we return true if they're not we return false so the problem is pretty simple now how exactly do we get these sequences so given a tree the main problem we have is how do we get the Leaf sequence because if we can do that then we can easily compare between the two trees and solve the problem well when it comes to trees how many ways do you even know to Traverse a tree there are variations but the main two ways breath for search and depth for search at first you might think that breath for search would work but it's actually more tricky than you might think let's quickly walk through it BFS otherwise known as level order traversal basically goes through every level of the tree which at first seems like it would work we'd get these nodes 674 and by the way we would know that these are nodes that we're going to add to the leaf similar sequence because these are the nodes that don't have any children so we'd go from left to right left to right and then here left to right add each of these cuz they don't have children then get to two it does have children so don't add it and then we'd get these two as well so this is like the leaf sequence we could do the same thing for the left tree and this time though we'd see Okay add six to the leaf sequence then get to two then add 9 and8 to the sequence and then lastly we'd add these two so basically with breath for search we don't guarantee that all of the leaf nodes are on the same level so the order gets kind of messed up if we try to process it that way so this is how we kind of narrow it down and we go with depth for search which does work pretty easily the idea here is pretty much the same we're going to start at the root of a tree go left and then right and every time with depth for search we know we just keep going left until we can't go left anymore so from here we'd go down here and this time we do the same thing if we get to a leaf node we'd add it to the result so right now we'd have six then we'd go back back up to the parent and then here we'd go down to seven add seven then go back up to the parent and now start doing the right side of the tree so this way you can already kind of tell we will guarantee that we will reach each of these Leaf nodes from left to right with recursive depth for search so now we go to one then we go left to four add four to the result then go back up we're at two then go left this is a leaf node add it to the result nine then go back down right and add eight we can do the same thing with this tree I'll quickly do that so here we go left not a leaf node here we go left again six it's a leaf node go back up go right at two down to seven it's a leaf node add it go back up two now down to four it's also a leaf node and then we go all the way back up to the root and now we're at one go left add nine and lastly go back up and add eight so this way it's okay if the leaf nodes are on different levels of the tree we can still get the outputs pretty easily and once we have these we can pretty much just compare these two arrays if they are equal we can return true otherwise we return false doing this type of traversal on each of these trees will require us visiting every node let's say the size of the first tree is n and the size of the second tree is M we would take both of them together and add them up for the time complexity for the space complexity we will say the height of the first tree let's say that's H1 and H2 is the height of the second tree because we will need that for the recursive call stack but actually now that I think of it we will have to add each of the levels of each tree into an array if we want to do the comparison so in the worst case actually the memory complexity also becomes n + m you might be wondering why is that well the last level of a tree if it's a complete binary tree ends up being half the size of the entire tree which this is a linear so that's how I'm getting the same thing for the memory complexity now let's code it up so I'm going to first write our recursive DFS we will pass in the root of a single node and we will pass in a second variable which is going to be a array and we're going to be populating that array from within this function so before we even Implement DFS let me just show you what we're going to do we're going to have Leaf one leaf 2 these are both going to be empty arrays initially each of them is corresponding to one of the trees and we will call DFS from Route One and pass in leaf one do the same thing for the second tree and pass in leaf two and then at the end in Python we can simply compare arrays like this we can literally just do the equality operator if they're both the same we return true if not it'll be false so now the only thing left to do is implement this DFS which will populate each of these arrays so first is the base case with trees it's usually the same if we have an empty tree let's just return okay the other case is also important to us if we reach a leaf node so if not root. left and not root. right we also return because it's a leaf node we don't need to go any further but before we do that let's add this node the value of the node in particular to the array that's passed in okay otherwise what we do is just call DFS on the left subtree passing in leaf and call DFS on the right subtree also passing and leave this is the entire code let's run it to make sure that it works okay unfortunately I made a dumb mistake and did not put the knot in front of this that's when the tree is actually empty otherwise we're always going to be returning sorry about that that's my bad now let's rerun this as you can see on the left it works and it's pretty efficient if you found this helpful please like And subscribe if you're preparing for coding interviews check out NE code. thanks for watching and I'll see you soon
Original Description
🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews
🧑💼 LinkedIn: https://www.linkedin.com/in/navdeep-singh-3aaa14161/
🐦 Twitter: https://twitter.com/neetcode1
⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf
Problem Link: https://leetcode.com/problems/leaf-similar-trees/
0:00 - Read the problem
1:14 - Drawing Explanation
5:06 - Coding Explanation
leetcode 872
#neetcode #leetcode #python
Watch on YouTube ↗
(saves to browser)
Sign in to unlock AI tutor explanation · ⚡30
Playlist
Uploads from NeetCodeIO · NeetCodeIO · 0 of 60
← Previous
Next →
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
Design Linked List - Leetcode 707 - Python
NeetCodeIO
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
LFU Cache - Leetcode 460 - Python
NeetCodeIO
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
IPO - Leetcode 502 - Python
NeetCodeIO
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
Sort an Array - Leetcode 912 - Python
NeetCodeIO
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO
Related AI Lessons
⚡
⚡
⚡
⚡
Bloom Filters, Explained Properly
Dev.to · Daksh Gargas
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Medium · Programming
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
Medium · Programming
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Medium · Python
Chapters (3)
Read the problem
1:14
Drawing Explanation
5:06
Coding Explanation
🎓
Tutor Explanation
DeepCamp AI