Maximum Depth of Binary Tree

main.md

Question

Approach

my approach was to use bottom-up --finding the depth of the subtrees for each node--. I used recursion for the approach

Algorithm

• if root is None:
  • return 0
• leftHeight = self.maxDepth(root.left)
• rightHeight = self.maxDepth(root.right)
• return 1 + max(leftDepth, rightDepth)

Implementation

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        leftDepth = self.maxDepth(root.left)
        rightDepth = self.maxDepth(root.right)

        return 1 + max(leftDepth, rightDepth)

Complexities

• Time: 𝑂(N) where N is the number of nodes
• Space: 𝑂(H) where H is the height of the tree