| Question | 104. Maximum Depth of Binary Tree – Leetcode Javascript Solution |
| Difficulty | Easy |
| Question Type | Tree, Binary Tree |
| Question Link | https://leetcode.com/problems/maximum-depth-of-binary-tree/ |
Problem Description :
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Explanation: From root node, we have total 3 levels(max depth of tree).Example 2:
Input: root = [1,null,2]
Output: 2
Explanation: From root node, we have total 2 levels.Constraints:
The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100Solution 1 (Using BFS) –> [non-recursive] :
var maxDepth = function(root) {
// iterative (BFS)
var queue = [];
queue.push(root);
var cur = {}; // tree node, object
var count = 0, size, i;
if (root !== null && root !== undefined) { // when root is null/undefined, return 0
while (queue.length > 0) {
// loop through all adjacent nodes of cur (binary tree, at most 2) --- from book
// let's record the size of queue for now, and after looping through all same-level nodes, count++
// this meets if there is only 1 root node as well
size = queue.length;
for (i = size; i > 0; i--) {
// dequeue, get the head of the node in queue out(FIFO)
cur = queue.shift();
if (cur.left !== null && cur.left !== undefined) {
queue.push(cur.left);
}
if (cur.right !== null && cur.right !== undefined) {
queue.push(cur.right);
}
}
count++; // same-level nodes all looped, count++
}
}
return count;
};Complexity Analysis :
Time complexity: O(n)
Space complexity: O(n)
Since our goal is to find maximum depth of tree, Breadth First Search(BFS) is good approach while solving Tree based problems. But, BFS will visit all childrens in each level of tree. Though it is good to use BFS on Trees, but finding maximum depth choosing Depth First Search(DFS) will be the better solution to bring up faster and better time and space complexity.
Solution 2 ( Using DFS ) : ==> Optimized
Using Depth First Search(DFS), we are calculating maximum height of tree as recursively.
- Recursively calculate the height of the tree to the left of the root.
- Recursively calculate the height of the tree to the right of the root.
- Pick the larger height from the two answers and add one to it (to account for the root node).
const maxDepth = function(root) {
let currentDepth = 0;
return dfsMaxDepth(root, currentDepth);
};
const dfsMaxDepth = function(node, currentDepth){
if(!node){
return currentDepth;
}
currentDepth++;
return Math.max(dfsMaxDepth(node.right, currentDepth), dfsMaxDepth(node.left, currentDepth));
}Complexity Analysis :
Time complexity: O(n)
Space complexity: O(n)
In the best case of time complexity, we can achieve by O(logn), since we are using binary tree to divide and conquer approach. In Worst case, we might need to traverse all nodes of the tree, so in that case we will be having O(n) time complexity.
As we are using recursive approach, our Space complexity will be O(n).
DFS is better approach compare to BFS, while finding depth of tree.
If you have any doubts, add in comment section. Will clarify at my level best. Also, if you have better solution, kindly share it, will grow together as to become better engineer.
