Check Completeness of a Binary Tree - Leetcode 958 - Python
Key Takeaways
Checks completeness of a binary tree using Python
Full Transcript
hey everyone welcome back and let's write some more neat code today so today let's solve the problem check completeness of a binary tree we're given the root of a binary tree and we just want to check if it is a complete binary tree which by definition is a tree where every single level in the tree is completely full except possibly the last level if the last level is not full then it has to be filled from left to right so here you can see it does have a single missing node but the missing node is all the way on the right side so the existing nodes are filled in from the left side now suppose this node over here was missing then it's not a complete binary tree because we have a node here but we also have a node here they're not filled from left to right we have a missing one right here now if we had all four nodes then it is all Al a complete binary tree so conceptually this problem is pretty simple by looking at it it's pretty easy to tell if we have a complete binary tree or not and algorithmically we know there's not a ton of different algorithms we can run on a binary tree usually it's DFS but the less common one is breath for search which one do you think is going to be more useful in this case probably breath for search which is basically a level order traversal we're going to Traverse it level by by level because that's probably what's going to allow us to know if the last level is filled from left to right so suppose we have the same binary tree over here well structurally the same the values are pretty much irrelevant so I'm not even going to put them in here because they just serve as a distraction for us in this problem as we're doing a breath first search on this problem we're going to have a Q data structure this is going to be inside of our Q we're going to pop this and then add its two children to the queue and then we're going to pop the left child over here and then append its children to the queue and then we're going to pop this next guy over here append its children it has one child here and it has null over here and then we're going to pop this guy and pop this guy and pop this guy and also append their children which are going to be null and then once we have a queue full of nulles which is what's going to happen in this case that's how our algorithm is going to terminate but how do we know at the end is it a complete binary tree or not well think about it like this for the last level we expect that eventually we will have some null either there's going to be a null here which is going to be the case for this problem or maybe this entire level is going to be full we have a node over here but then the last level is just going to be full of nulls so basically when we reach our first null value we expect that every other value we pop after that is also going to be null that's how you know it's a complete binary tree whether it's in the last level or whether it's in like the existing level maybe this node doesn't exist either we have two null values over here we expect they're not to be a situation like this where there's an existing node here but there's not a node here we pop this guy it's non-null we pop this guy it's nonnull we pop this it's a null value and then after that we do not expect to see a nonnull value over here if we do then it's not a complete binary tree now there's one last Edge case you might be thinking about what if we have a situation like this where yes there's a null in this level but what if this is not the last level what if over here this node also has a couple nonnull children does the algorithm I just described still work for this tree Let's test it out let's say we pop all of these and then we get to this level we pop this append its two children pop this append its two children which are null pop this append its children and then we get here we pop it we see okay it's a null value now we expect that everything we pop should also be null and if it's not the case that means this is not a complete binary tree so next we're going to pop these two notice how it's not null so that means this is not a complete binary tree so you can see that this pretty basic algorithm does work for pretty much every structure it will tell us whether a tree is a complete binary tree or not and since we're just doing a pretty basic breadth for search the overall time complexity is going to be Big O of n that's also going to be the memory complexity in the worst case so now let's code it up so as with every breath for search you want to start with a Q we're guaranteed that the root is going to be nonnull but that wouldn't matter the way I'm going to code this up anyway but I'm going to initialize this Q with the root value we have to pass in an array to initialize the Q so next we're going to run our breath for search while the Q is nonempty we're going to pop from the Q we pop from the left side because we're going to be pushing to the right side it's important to do it this way because we want to Traverse every level from left to right so when we pop the node we want to take the nodes children and append them to the CU so node. left and append node. right but it's possible as we're appending children to the Q that we end up appending a null value to the Q it's also possible that the root could have been null so before we try appending its children we have to first make sure that the node itself is nonnull so let's make sure if the node is non-null then we append its children but what if the node is null remember that's important because that's what's going to tell us whether we have a complete binary tree or not so when we do have a null node then we're going to run some different logic here at this point we expect every node that we pop to be null so we're going to say while Q let's just do the same thing we kind of did up above here except we're going to do it slightly differently we're going to say Q pop left we're also going to call this node but that's not really super important but we want to make sure that this thing we're popping and actually we don't even need to assign it to a variable we're going to check if this node that we just popped is non null then we have to return false because we were expecting everything to be null but now we found a non-null node that means this is not a complete binary tree so we return false now if we never execute this meaning we never execute this false we're definitely going to execute this while loop then our Q is going to be empty then we're going to come up up here and we're going to exit out of this loop as well and then out here we can go ahead and return true because we know we do have a complete binary tree so now let's run it to make sure that it works and as you can see yes it does it's pretty efficient even though the run times on leak code are random if this was helpful please like And subscribe if you're preparing for coding interviews check out n code. 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/ - A better way to prepare for Coding Interviews
🥷 Discord: https://discord.gg/ddjKRXPqtk
🐦 Twitter: https://twitter.com/neetcode1
🐮 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/check-completeness-of-a-binary-tree/
0:00 - Read the problem
1:20 - Drawing Explanation
5:10 - Coding Explanation
leetcode 958
#neetcode #leetcode #python
Watch on YouTube ↗
(saves to browser)
Sign in to unlock AI tutor explanation · ⚡30
Playlist
Uploads from NeetCodeIO · NeetCodeIO · 50 of 60
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
▶
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 Reads
Chapters (3)
Read the problem
1:20
Drawing Explanation
5:10
Coding Explanation
🎓
Tutor Explanation
DeepCamp AI