binarytree_diameter.py

"""Binary Tree: Longest path

https://link.medium.com/tHhd8C0KOU
"""

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = 
        self.right = None


class BinaryTree(object):
    def __init__(self):
        self.root = None
        self._diameter = 0

    @classmethod
    def _print(cls, node):
        if node.left:
            cls._print(node.left)
        print(node.value, end=' ')
        if node.right:
            cls._print(node.right)

    @classmethod
    def _clear(cls, node):
        if node.left:
            cls._clear(node.left)
            node.left = None
        if node.right:
            cls._clear(node.right)
            node.right = None

    def _find_diameter(self, node):
        if not node:
            return 0

        left = self._find_diameter(node.left)
        right = self._find_diameter(node.right)

        # print(f'node = {node.value}, left={left}, right={right}, d={self._diameter}')

        if left + right > self._diameter:
            self._diameter = left + right

        if left > right:
            return 1 + left
        else:
            return 1 + right

    def print(self):
        self._print(self.root)
        print()

    def clear(self):
        self._diameter = 0
        self._clear(self.root)
        self.root = None

    def add(self, value):
        if not self.root:
            self.root = Node(value)
            return

        current = self.root
        previous = self.root

        while current:
            previous = current
            if value < current.value:
                current = current.left
                if not current:
                    previous.left = Node(value)

            else:
                current = current.right
                if not current:
                    previous.right = Node(value)

    def find_diameter(self):
        self._diameter = 0
        self._find_diameter(self.root)
        return self._diameter


if __name__ == '__main__':
    tests = [
        [100, 150, 50, 75, 125, 74, 73, 76, 124, 130, 131],
        [100, 50, 150, 25, 75, 125, 175, 12, 70, 78, 123, 128, 225, 5, 65, 73, 79, 122, 126, 129, 250, 0, 275],
        [100, 75, 125, 50, 87, 112, 150, 25, 175],
        [100, 125, 75, 80, 85, 90, 70, 65, 60]
    ]

    bt = BinaryTree()
    for i, test in enumerate(tests, 1):
        for value in test:
            bt.add(value)

        print(f'Test #{i}:')
        print('  ', end='')
        bt.print()
        print(f'  Diameter: {bt.find_diameter()}')
        print()

        bt.clear()

Output:

Test #1:
  50 73 74 75 76 100 124 125 130 131 150 
  Diameter: 8

Test #2:
  0 5 12 25 50 65 70 73 75 78 79 100 122 123 125 126 128 129 150 175 225 250 275 
  Diameter: 10

Test #3:
  25 50 75 87 100 112 125 150 175 
  Diameter: 6

Test #4:
  60 65 70 75 80 85 90 100 125 
  Diameter: 6