C++: Diameter of Binary Tree

Thought Process

To find the diameter of a binary tree, we can use a recursive approach. The diameter of a tree is the longest path between any two node, which may or may not pass through the root. We calculate the height of each subtree recursively and update the diameter as the maximum sum of the heights of the left and right subtrees. 

/**
 * 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 diameter = 0;
    int height(TreeNode* root){

        if(root==NULL)
            return 0;

        int leftHeight = height(root->left);
        int rightHeight = height(root->right);

        diameter = max(diameter,leftHeight+rightHeight);
        return 1+max(leftHeight,rightHeight);
    }

    int diameterOfBinaryTree(TreeNode* root) {

        if(root==NULL)
            return 0;

        int ht = height(root);
        return diameter;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(h)

The space used by the recursion stack depends on the height of the tree (h). In the worst case (a skewed tree), the space complexity is O(n).

Code copied!