algoadvance

Leetcode 543. Diameter of Binary Tree

Problem Statement

The problem statement for “Diameter of Binary Tree” on LeetCode is as follows:

Given the root of a binary tree, return the length of the diameter of the 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.

The length of a path between two nodes is represented by the number of edges between them.

Clarifying Questions

Before we dive into the solution, let’s clarify a few things:

  1. What is the definition of the length of the path?
    • The length is defined as the number of edges between the two nodes.
  2. Can the binary tree be empty?
    • Yes, the binary tree can be empty, in which case the diameter would be 0.
  3. Is it guaranteed that the tree will be a binary tree?
    • Yes, the tree is a binary tree as stated in the problem.

Strategy

To solve the problem, we can use a depth-first search (DFS) approach. The idea is to:

  1. Define a recursive function that computes the height of each subtree.
  2. As part of the height calculation, determine the diameter at each node by summing the heights of the left and right subtrees.
  3. Maintain a global variable to keep track of the maximum diameter found during the traversal.

Detailed Steps

  1. Define a helper function height(node):
    • If the node is null, return 0.
    • Recursively find the heights of the left and right subtrees.
    • Update the global diameter by comparing it with the sum of left and right heights.
    • Return the height of the tree rooted at the current node.
  2. Initialize the diameter to 0 at the start and then return it after the DFS completes.

Code

#include <algorithm> // for max

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0; // Global variable to store the diameter
        height(root, diameter);
        return diameter;
    }

private:
    int height(TreeNode* node, int& diameter) {
        if (node == nullptr) return 0;

        int leftHeight = height(node->left, diameter);
        int rightHeight = height(node->right, diameter);

        // Update the diameter
        diameter = std::max(diameter, leftHeight + rightHeight);

        // Return the height of the tree
        return std::max(leftHeight, rightHeight) + 1;
    }
};

Time Complexity

The time complexity of this solution is O(N), where N is the number of nodes in the binary tree. This is because we traverse each node exactly once during the depth-first search to compute the heights and simultaneously update the diameter.

Space Complexity

The space complexity is O(H), where H is the height of the binary tree. This accounts for the recursive stack space used during the depth-first search. In the worst case (skewed tree), the height can be N, making the space complexity O(N). In the average case, for a balanced tree, it would be O(log N).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI