Count Complete Tree Nodes | LeetCode 222 | C++, Java, Python
Vložit
- čas přidán 22. 06. 2020
- LeetCode Solutions: • LeetCode Solutions | L...
June LeetCoding Challenge: • Playlist
May LeetCoding Challenge: • Playlist
Github Link: github.com/KnowledgeCenterYou...
*** Best Books For Data Structures & Algorithms for Interviews:*********
1. Cracking the Coding Interview: amzn.to/2WeO3eO
2. Cracking the Coding Interview Paperback: amzn.to/3aSSe3Q
3. Coding Interview Questions - Narasimha Karumanchi: amzn.to/3cYqjkV
4. Data Structures and Algorithms Made Easy - N. Karumanchi: amzn.to/2U8FrDt
5. Data Structures & Algorithms made Easy in Java - N. Karumanchi: amzn.to/2U0qZgY
6. Introduction to Algorithms - CLR - Cormen, Leiserson, Rivest: amzn.to/2Wdp8rZ
*****************************************************************************
June LeetCoding Challenge | Problem 23 | Count Complete Tree Nodes | 23 June,
Facebook Coding Interview question,
google coding interview question,
leetcode,
Count Complete Tree Nodes,
Count Complete Tree Nodes c++,
Count Complete Tree Nodes Java,
Count Complete Tree Nodes python,
Count Complete Tree Nodes solution,
222. Count Complete Tree Nodes,
#Facebook #CodingInterview #LeetCode #JuneLeetCodingChallenge #Google #Amazon #CompleteBinaryTree
Time complexity?
Interested to know which software do u use to explain and write on
Loved the optimization part.I thought it is just a simple traversal problem.
Please talk about time complexity after the code complete.
Very nicely explained!!
Thank you 🙂
Thanks for the explanation. It nice and easy to understand.
Can you tell me the software you use to create these videos?
powerpoint
The simple recursive solution : as follows
If(root==null) return 0;
Return 1+countNodes (root.left)+countNodes (root.right);
As I said in the video, any traversal will work. But, we should optimize the solution by utilizing Completeness property whenever possible.
For complete Binary Tree with all levels filled, it will take O(logn) time, bu for a normal Binary Tree, it will be O(n).
So, check if a given subtree is complete and filled, return 2^h - 1, else keep traversing.
@@KnowledgeCenter it's really good approach . thanks
pbs.twimg.com/media/DgG54TGUcAAKAUE.jpg Sorry I had too 😂
Binary search is more optional one
*A faster approach*
_As you don't require two traverse twice in every recursive call_
public class Solution {
public int CountNodes(TreeNode root) {
if(root == null)
return 0;
TreeNode leftNode = root, rightNode = root;
int height = 0;
while(rightNode != null) {
height++;
rightNode = rightNode.right;
leftNode = leftNode.left;
}
if(leftNode == null)
return (1
consider tree with no left node it has all node on right. then this code will throw NPE, right?