Grokking 75: Top Coding Interview Questions
Vote

0% completed

​

Tree Diameter (easy)

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.

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:

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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
A

Anonymous

· 4 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

Anonymous

· 4 years ago

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

Show 3 replies
A

Anonymous

· 5 years ago

if leftTreeHeight is not None and rightTreeHeight is not None:

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

Show 2 replies

Reading Progress

0%

Vote for new content