Maximum Depth of Binary Tree (LeetCode 104) | Full Solution with animations | Study Algorithms
HTML-код
- Опубликовано: 2 авг 2024
- The underlying concept to finding the maximum depth is to find the height of a binary tree and is a very basic concept which is used in a lot of preliminary analysis. You can approach this problem using a recursive technique or an iterative technique. One can also see the height of a tree as the deepest level in a binary tree. This video takes advantage of the level order traversal technique to find the height of a binary tree.
Actual Problem on LeetCode: leetcode.com/problems/maximum...
Chapters:
00:00 - Intro
01:31 - Problem statement and description
03:34 - Brute Force approach to find the height of a binary tree
06:05 - Efficient method
09:19 - Dry-run of Code
14:18 - Final Thoughts
📚 Links to topics I talk about in the video:
Understanding Tree Data Structure: • Understanding Tree Dat...
Level Order Traversal: • Level order traversal ...
Recursion Algorithmic Paradigm: • Recursion paradigms wi...
Tree Data Structure: • Understanding Tree Dat...
Playlist on Trees: • Trees
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
🔗 To see more videos like this, you can show your support on: www.buymeacoffee.com/studyalg...
🎥 My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #binarytrees
You are great man! I am amazed the way you simply the problems.
Finally, I understand this implementation. Thank you so much 🙏!!
Thank man!
nice video nikhil sir!!!
Bro i have exam for amadeous next month plz help me in preparation in coding. you're the only one who taught me algorithms clearly.plzz bro😢😢
Thanks
Helpful man!
Glad to hear it!
how to calculate the distance between the root and each of the leaf nodes in the brute-force approach?
you keep on traversing each direction, until you find the desired leaf node
plz don't mind, this 14th and 11th from this playlist are the same right?
Yes. His intention is to convey that the same problem can be asked in two ways: Maximum Depth of Binary Tree, Height of binary tree.
Loved your all the videos. But this code has one flaw. If you see the queue size will never be zero until it reached leaf node as we are enqueuing it simultaneously will children nodes, as a result height will never increment to its correct value.
It is always the correct value. The code passes all cases on LeetCode. Can you elaborate more?
Height of Binary tree is the number of edges along the longest path from root to leaf
Max Depth of Binary tree is the number of nodes along the longest path from root to leaf
Max Depth = Height + 1
So the answer should be 3 right for the example you have given
These terms will be used interchangeably…but you get the correct idea 👍
@@nikoo28 bor even my test cases are not passing its showing wrong, please do help me in this once..
@@chiruchiruchiranjeevi3237 You probably have to check for an empty tree (root == null)
all you gotta do is change the numberOfLevels to be initialized as 0 instead of -1 and it should all work. 0 for depth, -1 for height.@@chiruchiruchiranjeevi3237
Height of Binary tree is the number of edges along the longest path from root to leaf
but why we adding 1 also leaf node.which is wrong correct?
def height(root):
# Base case: Empty tree has a height equals 0
if root is None:
return 0
# Calling Left and Right node recursively
return 1 + max(height(root.left), height(root.right))
i did not understand your question. The 1 actually accounts for your count. If you do not have that..the result will always be 0
How does an TreeNode "element" represent an "int" if int value is stored in the element.val (int val) inside a TreeNode object? Are we not supposed to reference the int value with element.val?
What do you mean? If the element.val is int, it will be of the int type.
Can you clarify your question please
@@nikoo28 Thank you so much for replying! I will give an example from your code: if you add to queue elementQueue.add(root), isn't it supposed to be elementQueue.add(root.val)? How does it retrieve the integer from just a "root" TreeNode object if we do not reference exactly to the value(root.val)?
public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
....... etc.
that is because if you retrieve the root, you will get a TreeNode object. you can then fetch the value using ".val"
int maxDepth(TreeNode* root) {
int maxDepth = 0; // Initialize the maximum depth
int count = 0; // Initialize the current depth counter
dfs(root, count, maxDepth);
return maxDepth;
}
private:
void dfs(TreeNode* node, int count, int &maxDepth) {
if (node == NULL) return;
count++; // Increment counter to reflect current depth
if (count > maxDepth) {
maxDepth = count; // Update maximum depth
}
dfs(node->left, count, maxDepth);
dfs(node->right, count, maxDepth);
}
}; bhaiya this code works but i cant understand how every recursion call maintain its own count variable
any resource on building this basic type of binary tree? i find it harder to build it than binary search trees that split the values based on their size to left and right subtrees