Diameter of Binary Tree

Data Structures and Algorithms

Statement

Given a binary tree, find the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. The path may or may not pass through the root.

Constraints

• 1 ≤ number of nodes in tree ≤ 500
• -100 ≤ node.value ≤ 100

Solution

"""
production algorithm
"""


class Solution:
    def diameter_of_binary_tree(self, root):
        """
        time complexity O(n)
        space complexity O(n)
        """
        _, diameter = self.diameter_of_binary_tree_helper(root)
        return diameter

    def diameter_of_binary_tree_helper(self, root):
        """
        time complexity O(n)
        space complexity O(n)
        """
        if root is None:
            return -1, 0
        lheight, ldiameter = self.diameter_of_binary_tree_helper(root.left)
        rheight, rdiameter = self.diameter_of_binary_tree_helper(root.right)
        return 1 + max(lheight, rheight), max(2 + lheight + rheight, ldiameter, rdiameter)

"""
unit tests
"""

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


class SolutionTestCase(TestCase):
    def test_diameter_passes_through_root(self):
        # Given
        root = BinaryTreeNode(1)
        root.left = BinaryTreeNode(2)
        root.right = BinaryTreeNode(3)
        root.left.left = BinaryTreeNode(4)
        root.left.right = BinaryTreeNode(5)
        root.right.left = BinaryTreeNode(6)
        root.right.right = BinaryTreeNode(7)
        root.left.left.left = BinaryTreeNode(8)
        root.left.right.left = BinaryTreeNode(9)
        root.right.left.left = BinaryTreeNode(10)
        root.right.right.left = BinaryTreeNode(11)
        solution = Solution()

        # When
        actual = solution.diameter_of_binary_tree(root)

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

    def test_diameter_doesnt_pass_throuh_root(self):
        # Given
        root = BinaryTreeNode(1)
        root.left = BinaryTreeNode(2)
        root.right = BinaryTreeNode(3)
        root.right.left = BinaryTreeNode(4)
        root.right.right = BinaryTreeNode(5)
        root.right.right.left = BinaryTreeNode(6)
        root.right.right.right = BinaryTreeNode(7)
        root.right.right.left.left = BinaryTreeNode(8)
        root.right.right.right.left = BinaryTreeNode(9)
        root.right.right.left.left.left = BinaryTreeNode(10)
        root.right.right.right.left.left = BinaryTreeNode(11)
        root.right.right.left.left.left.left = BinaryTreeNode(12)
        root.right.right.right.left.left.left = BinaryTreeNode(13)
        solution = Solution()

        # When
        actual = solution.diameter_of_binary_tree(root)

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

Strategy

Depth First Search.

Explanation

The algorithm recurses to the bottom of the binary tree. This is where summation of the height and diameter begins. Each step of recursion returns the maximum height and diameter seen so far. When recursion from the root node returns, then the maximum diameter is returned.

Time Complexity

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

Space Complexity

The depth of recursion can reach size n, where n is the number of nodes in the binary tree. Therefore, the auxiliary space complexity of the algorithm is O(n).

Links

data_structures_algorithms/algorithms/dfs/diameter_of_binary_tree at main ·…