algoadvance

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

Details:

• Each node in the binary tree has an integer value.
• The node structure is defined as follows:

  class TreeNode:
      def __init__(self, val=0, left=None, right=None):
          self.val = val
          self.left = left
          self.right = right
  

Function Signature:

def diameterOfBinaryTree(root: TreeNode) -> int:

Example: Given a binary tree:

        1
       / \
      2   3
     / \     
    4   5    

The longest path is [4, 2, 1, 3] or [5, 2, 1, 3], and the length of this path is 3.

Strategy

1. We will use Depth-First Search (DFS) to traverse the tree.
2. While traversing, for each node, we will compute the depth of its left and right subtrees.
3. The diameter through the current node will be the sum of the maximum depths of its left and right subtrees.
4. We will maintain a variable to track the maximum diameter encountered during the traversal.
5. The final result will be the maximum diameter recorded.

Steps:

1. Define a helper function depth(node) that computes the depth of the tree originating from the given node.
2. During each call to depth(node), compute the depths of the left and right children.
3. Update the maximum diameter while considering the sum of the depths of the left and right children.
4. Return the depth of the current node which is 1 + max(depth of left child, depth of right child).
5. The main function diameterOfBinaryTree will initialize the maximum diameter and invoke the helper function starting from the root.

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diameterOfBinaryTree(root: TreeNode) -> int:
    # This variable will hold the maximum diameter found
    max_diameter = 0

    def depth(node):
        nonlocal max_diameter
        if not node:
            return 0
        # Compute the depth of left and right subtrees
        left_depth = depth(node.left)
        right_depth = depth(node.right)
        
        # Compute the potential diameter at this node
        max_diameter = max(max_diameter, left_depth + right_depth)
        
        # Return the depth of this node
        return 1 + max(left_depth, right_depth)
    
    # Start the depth computation from the root
    depth(root)
    return max_diameter

Time Complexity

• The algorithm visits each node exactly once, hence the time complexity is ( O(N) ), where ( N ) is the number of nodes in the binary tree.
• The space complexity can be ( O(h) ) due to the recursion stack space, where ( h ) is the height of the tree. For a balanced tree, ( h ) is ( O(\log N) ), and for a skewed tree, ( h ) is ( O(N) ).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?