Maximum Depth of Binary Tree

Data Structures and Algorithms

Statement

Given the root of a binary tree, find the maximum depth of the tree.

Constraints

• 1 ≤ number of nodes ≤ 500
• -100 ≤ node.data ≤ 100

Solution

"""
production algorithm
"""


class Solution:
    def find_max_depth(self, root):
        """
        time complexity O(n)
        space complexity O(n)
        """
        return self.find_max_depth_helper(root)

    def find_max_depth_helper(self, root):
        """
        time complexity O(n)
        space complexity O(n)
        """
        if root is None:
            return 0
        return 1 + max(self.find_max_depth_helper(root.left), self.find_max_depth_helper(root.right))

"""
unit tests
"""

from unittest import TestCase
from algorithms.dfs.maximum_depth_of_binary_tree.solution import Solution
from data_structures.binary_tree.binary_tree import BinaryTreeNode


class SolutionTestCase(TestCase):
    def test_maximum_depth_is_zero(self):
        # Given
        root = None
        solution = Solution()

        # When
        actual = solution.find_max_depth(root)

        # Then
        expected = 0
        self.assertEqual(actual, expected)

    def test_maximum_depth_is_one(self):
        # Given
        root = BinaryTreeNode(0)
        solution = Solution()

        # When
        actual = solution.find_max_depth(root)

        # Then
        expected = 1
        self.assertEqual(actual, expected)

    def test_maximum_depth_is_five(self):
        # Given
        root = BinaryTreeNode(0)
        root.left = BinaryTreeNode(2)
        root.left.right = BinaryTreeNode(4)
        root.left.right.left = BinaryTreeNode(6)
        root.left.right.left.right = BinaryTreeNode(8)
        solution = Solution()

        # When
        actual = solution.find_max_depth(root)

        # Then
        expected = 5
        self.assertEqual(actual, expected)

Strategy

Depth First Search.

Explanation

The algorithm uses recursion, and for each step of recursion adds one to the maximum depth seen so far. The algorithm branches to the left and right subtrees, and the maximum depth of both subtrees is chosen in calculation of the maximum depth of the binary tree. The result of the algorithm is the maximum depth of the binary tree.

Time Complexity

The algorithm visits every node once. Therefore, the time complexity of the algorithm is O(n).

Space Complexity

In the case of a degenerate tree, the maximum depth of recursion is n, where n is the number of nodes in the tree. Therefore, the auxiliary space complexity of the algorithm O(n).

Links

data_structures_algorithms/algorithms/dfs/maximum_depth_of_binary_tree at main ·…