LeetCode 543: Diameter of a Binary Tree in C++

Quick Answer: To solve the LeetCode 543 Diameter of a Binary Tree problem in C++, you can use a Depth-First Search (DFS) algorithm. The diameter of a binary tree is the longest path between any two nodes. By calculating the height of the left and right subtrees at each node, you can determine the maximum diameter (left height + right height) while updating the global maximum. This approach yields an optimal time complexity of O(N).

Understanding the Diameter of a Binary Tree Problem

Given the root of a binary tree, return the length of the diameter of the tree. This is a common computer science and software engineering interview question that tests your understanding of tree traversals and recursion.

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.

Example 1:
Input: root = [1,2,3,4,5] Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].


Example 2:
Input: root = [1,2] Output: 1

Constraints:

-100 <= Node.val <= 100

The number of nodes in the tree is in the range [1, 104].

Optimized C++ Solution with Test Cases

Below is a highly optimized C++ implementation. By utilizing a recursive DFS (Depth-First Search) helper function, we traverse down to the leaf nodes and compute heights from the bottom up. At each node, we continuously update our global result variable to hold the maximum diameter encountered so far.

#include <iostream>
#include <algorithm>
using namespace std;

// 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 result;
    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        result = max(result, left + right);
        return max(left, right) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        result = 0;
        dfs(root);
        return result;
    }
};

// Helper function to create a tree
TreeNode* createTree() {
    /*
        Example tree:
                1
               / \
              2   3
             / \
            4   5
    */
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    return root;
}

int main() {
    // Create a sample binary tree
    TreeNode* root = createTree();

    // Create a Solution object
    Solution solution;

    // Call the diameterOfBinaryTree function
    int diameter = solution.diameterOfBinaryTree(root);

    // Output the result
    cout << "Diameter of the binary tree: " << diameter << endl;

    // Clean up memory (optional but good practice)
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

Frequently Asked Questions (FAQ)

What is the time complexity of this algorithm?

The time complexity is O(N), where N is the number of nodes in the binary tree. Since we are using a Depth-First Search strategy, we visit every single node in the tree exactly once to calculate its height.

What is the space complexity?

The space complexity is O(H), where H is the height of the tree. This accounts for the recursive call stack during the DFS traversal. In the worst-case scenario (a skewed tree), the space complexity would be O(N). For a perfectly balanced binary tree, the space complexity is O(log N).

Can the longest path exist entirely in one subtree?

Yes, absolutely. The definition of the diameter states it is the longest path between any two nodes. This path could completely reside within the left or right subtree without ever passing through the overall root node of the binary tree.