Maximum Depth Of Binary Tree

                                            
/**
 * 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 == nullptr) {
            return 0;
        }
        
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        
        return 1 + max(leftDepth, rightDepth);
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
*/

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

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int maxDepth(struct TreeNode* root) {
    if(root == NULL)
        return 0;
    
    int left_depth = maxDepth(root->left);
    int right_depth = maxDepth(root->right);
    
    return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null)
            return 0;
        return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));
    }
}

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

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function maxDepth(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }
    
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) {
 *         $this->val = $value;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function maxDepth($root) {
        if ($root == null) {
            return 0;
        }
        $leftDepth = $this->maxDepth($root->left);
        $rightDepth = $this->maxDepth($root->right);
        return max($leftDepth, $rightDepth) + 1;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */

class Solution {
    func maxDepth(_ root: TreeNode?) -> Int {
        guard let root = root else {
            return 0
        }
        
        let leftDepth = maxDepth(root.left)
        let rightDepth = maxDepth(root.right)
        
        return 1 + max(leftDepth, rightDepth)
    }
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   int val;
 *   TreeNode? left;
 *   TreeNode? right;
 *   TreeNode(this.val, {this.left, this.right});
 * }
 */

class Solution {
  int maxDepth(TreeNode? root) {
    if (root == null) {
      return 0;
    }
    
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    
    return 1 + max(leftDepth, rightDepth);
  }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    leftDepth := maxDepth(root.Left)
    rightDepth := maxDepth(root.Right)
    
    if leftDepth > rightDepth {
        return leftDepth + 1
    }
    return rightDepth + 1
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left, @right = left, right
#     end
# end

def max_depth(root)
    return 0 if root.nil?
    
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    
    return 1 + [left_depth, right_depth].max
end

                                            
use std::cmp::max;
use std::rc::Rc;
use std::cell::RefCell;

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }

impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match root {
            Some(node) => {
                let node = node.borrow();
                1 + max(Solution::max_depth(node.left.clone()), Solution::max_depth(node.right.clone()))
            }
            None => 0
        }
    }
}

                                            
%% Definition for a binary tree node.
%%
%% -record(tree_node, {val = 0 :: integer(),
%%                     left = null  :: 'null' | 'tree_node',
%%                     right = null :: 'null' | 'tree_node'}).

max_depth(null) -> 0;
max_depth(#tree_node{left = L, right = R}) -> 1 + max(max_depth(L), max_depth(R)).

To solve this coding challenge, we need to determine the maximum depth of a binary tree. The maximum depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node. Here's how you can approach and solve this problem using a recursive traversal method.

Explanation

Understanding the Problem :

The challenge requires calculating the maximum depth of a binary tree.
Depth is measured by the number of edges along the longest path from the root node to a leaf node.

Recursive Approach :

A recursive function can be used to traverse the tree. For each node, we calculate the maximum depth of the left subtree and the right subtree.
The base case for the recursion would be an empty tree (where the root is
null

), and the depth in this case would be 0.
For each non-null node, the depth would be 1 plus the maximum depth of its left and right subtrees.

Steps to Solve :

If the current node is
null

, return a depth of 0.
Recursively calculate the maximum depth of the left subtree.
Recursively calculate the maximum depth of the right subtree.
The depth of the current node is 1 plus the maximum of the depths of its left and right subtrees.

Complexity :

Since we visit each node exactly once, the time complexity is O(n), where n is the number of nodes in the tree.
The space complexity is O(h) for the call stack, where h is the height of the tree. In the worst case (unbalanced tree), this can be O(n).

Detailed Steps in Pseudocode

Define the recursive function :

Input: the current node (starting with the root of the tree).
Output: the depth of the tree starting from the current node.

Base Case :

If the node is
null

, return 0.

Recursive Case :

Calculate the depth of the left child.
Calculate the depth of the right child.
The depth of the current node is 1 plus the maximum of the depths of the left and right children.

Pseudocode with Comments

                                            
# Define a function to calculate the maximum depth of the binary tree
function maxDepth(root):
# Base case: if the current node is null, return 0
if root is null:
return 0

# Recursive case: calculate the depth of the left subtree
left_depth = maxDepth(root.left)

# Recursive case: calculate the depth of the right subtree
right_depth = maxDepth(root.right)

# The depth of the current node is 1 plus the maximum of left_depth and right_depth
return 1 + max(left_depth, right_depth)

Step-by-Step Explanation

Invoke the Function :

Start by calling
maxDepth

with the root of the tree.

Base Case Handling :

If the input node (initially the root) is
null

, the function immediately returns 0, indicating no depth.

Recursive Calculation :

When the node is not
null

, the function calls itself to determine the depths of the left and right subtrees.
For each call, the function continues to go deeper into the tree until it reaches the leaf nodes (nodes with no children).

Combining Results :

After reaching the leaf nodes and returning from the base case, the function calculates the depth for the parent nodes.
The depth for any node is determined as 1 plus the greater of the depths from its left and right children.

Return Final Result :

As the recursive calls unwind, the function ultimately returns the depth of the entire tree, starting from the root.

This detailed explanation and pseudocode should help you understand how to approach and solve the problem of finding the maximum depth of a binary tree.