Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Problem Challenge 1: Tree Diameter (medium)

Problem Statement

Try it yourself

Problem Statement

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

Note: You can always assume that there are at least two leaf nodes in the given tree.

Image
Image

Constraints:

  • n == edges.length + 1
  • 1 <= n <= 10<sup>4</sup>
  • 0 <= a<sub>i</sub>, b<sub>i</sub> < n
  • a<sub>i</sub> != b<sub>i</sub>

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
Mark as Completed
P

PENG SHI

· 4 years ago

if leftTreeHeight is not None and rightTreeHeight is not None:

should be if leftTreeHeight == 0 and rightTreeHeight == 0:

Show 2 replies
Jan Carlos Dominguez

Jan Carlos Dominguez

· 3 years ago

Hello.

I'm having issues understanding how in the example 2, node 1 and node 2 are not counted in the diamater. I know it is supposed to be the longest path between two leaf nodes but in the code I don't see how it is reflected.

Thanks in advanced.

Show 3 replies
A

Alan Lo

· 4 years ago

Would you mind comparing this problem and LeetCode's 543 ? https://leetcode.com/problems/diameter-of-binary-tree/

Show 3 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

from heapq import *

class Solution:
  
  def dfs(self, node, max_heap):
    # if leaf node
    if node and not node.left and not node.right:
      return 1

    left = right = 0 

    if node.left:
      left = self.dfs(node.left, max_heap)
    
    if node.right:
      right = self.dfs(node.right, max_heap)

    # heap is used to push the path lengths = left length + right length + node length = '1'
    heappush(max_heap, -(left + right + 1))

    return max(left, right) + 1

  def findDiameter(self, root):
    max_heap = []
    self.dfs(root, max_heap)
    return -heappop(max_heap)
Show 1 reply
Francisco

Francisco

· a month ago

class Solution:



    def findDiameter(self, root):

        self.treeDiameter = 0



        def height(node):

            if not node:

                return 0



            left = height(node.left)

            right = height(node.right)



            self.treeDiameter = max(

                self.treeDiameter,

                left + right + 1  # number of nodes on path

            )



            return 1 + max(left, right)



        height(root)

        return self.treeDiameter

On This Page

Problem Statement

Try it yourself