< Back




543. Diameter of Binary Tree

We get the root of a binary tree and are asked to find its diameter. The diameter is determined by
the number of edges between two nodes - we're looking for the maximum and it doesn't even have to
be from the root of the tree.

We maintain a global maximum because, like stated earlier, it's not guaranteed that the diameter of
the tree passes through the root. We conduct a depth-first search until we hit leaf nodes. Leaf
nodes return 0. All other nodes sum the results of the recursive function call from the left and
right nodes and update the global answer with the maximum.

At each node we return the maximum of the results from the left and right function call and add 1.
We add one because when we backtrack, we're backtracking to the parent node via the edge that we
account for.

The solution is as follows:


  class Solution:
      def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
          self.ans = float("-inf")

          def dfs(node: Optional[TreeNode]) -> int:
              if not node:
                  return 0

              left, right = dfs(node.left), dfs(node.right)
              self.ans = max(self.ans, left + right)

              return max(left, right) + 1

          dfs(root)
          return self.ans


_ Time Complexity:

  O(n) - We inspect all nodes in the binary tree.

_ Space Complexity:

  O(n) - Our call stack can grow to the size of the number of nodes in the tree.