Solution For Maximum Depth Of Binary Tree

Problem Statement:

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution:

This problem can be solved easily using a recursive approach. We can use Depth First Search (DFS) to calculate the maximum depth of the binary tree. We will calculate the depth of the left subtree and the depth of the right subtree recursively. Then we will take the maximum of these two values and add one to it, as the root node is at depth 1. The resulting value will be the maximum depth of the binary tree.

Here is the algorithm for calculating the maximum depth of a binary tree using DFS:

1. If the given binary tree is empty, return 0.
2. Calculate the depth of the left subtree recursively by calling the maximumDepth function on the left child of the root node.
3. Calculate the depth of the right subtree recursively by calling the maximumDepth function on the right child of the root node.
4. Take the maximum of the two depths and add one to it to get the maximum depth of the binary tree.
5. Return the maximum depth.

Here is the Python code for the above algorithm:

“`
class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def maximumDepth(root: TreeNode) -> int:
if root is None:
return 0
left_depth = maximumDepth(root.left)
right_depth = maximumDepth(root.right)
return max(left_depth, right_depth) + 1
“`

We have defined the TreeNode class to represent each node of the binary tree. The maximumDepth function takes the root node of the binary tree as input and returns the maximum depth of the binary tree.

We start by checking if the root node is empty. If it is, we return 0 as the depth.

Next, we calculate the depth of the left subtree recursively by calling the maximumDepth function on the left child of the root node. Similarly, we calculate the depth of the right subtree recursively by calling the maximumDepth function on the right child of the root node.

Once we have calculated the depths of the left and right subtrees, we take the maximum of the two values and add one to it to get the maximum depth of the binary tree.

Finally, we return the maximum depth.

This solution has a time complexity of O(n), where n is the number of nodes in the binary tree, as we visit each node once. The space complexity is O(h), where h is the height of the binary tree, as the maximum depth of the recursive call stack is equal to the height of the tree.

Step by Step Implementation For Maximum Depth Of Binary Tree

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

def maxDepth(root): 
    
    if root is None: 
        return 0 
    
    else: 
        
        # Compute the depth of each subtree 
        l_depth = maxDepth(root.left) 
        r_depth = maxDepth(root.right) 
    
        # Use the larger one 
        if (l_depth > r_depth): 
            return l_depth+1
        else: 
            return r_depth+1

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
 
 // recursive solution
var maxDepth = function(root) {
    if (root === null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)
            return 0;
        int lh=maxDepth(root->left);
        int rh=maxDepth(root->right);
        return max(lh,rh)+1;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int MaxDepth(TreeNode root) {
        //if the tree is empty, return a depth of 0
        if(root == null){
            return 0;
        }
        //if the tree is not empty, recursively call MaxDepth on the left and right subtrees
        //and return the maximum depth of the two
        else{
            return Math.Max(MaxDepth(root.left), MaxDepth(root.right)) + 1;
        }
    }
}