Solution by minions_


  • 4

    Approach #1 Brute Force [Time Limit Exceeded]

    Intuition

    Brute Force Approach would be to list out all possible permutation of paths between two nodes
    I.e. take all pairs of two nodes and find distance between them and finally print the largest distance.

    Complexity Analysis

    • Time complexity : $$O(n^3)$$.

    Taking permutation of two nodes will be O(n^2) and per two node finding distance would be O(n)
    So total would be O(n^3).

    • Space complexity : $$O(n)$$.

    Approach #2 O(n^2) [Accepted]

    Intuition

    Computing height of left and right subtree at each node
    Note
    height =number of vertices on the longest path from the node to a leaf
    Or recursively height = max(left subtree height , right subtree height) + 1
    Where NULL nodes have height 0 and leaf nodes have height 1
    For example:
    (0_1506392292167_1.png
    [img1.png]

    this tree have height as 3 for path 1 - 2 - 4 comprising of three nodes.

    Algorithm
    For each node there would be two cases

    1. the diameter passes through the node
    2. the diameter doesn’t passes through the node

    Case 1 : diameter passes through the node
    Then diameter would be height of left subtree + height of right subtree
    0_1506392310862_2.png
    [img2.png]

    For e.g. in above figure diameter is 3 as node 1 is part of path of diameter which is
    4 - 2 - 1 - 3
    Diameter = left subtree height (2) + right subtree height (1)

    Case 2 : diameter does not passes through the node
    If this is the case, then diameter would be
    maximum of (diameter of left subtree , diameter of right subtree)
    It is because there is some path in lower parts of tree which is longer than including
    current node.

    0_1506621609740_3.png

    For example in above figure diameter is 8 [10-8-6-4-2-5-7-9-11] and it is not passing through 1. Which is maximum of diameter of left tree (8) and right tree (0).

    So, for each node recursive formula would be maximum of three quantity

    1. Diameter of left subtree
    2. Diameter of right subtree
    3. Left subtree height + right subtree height

    Where first two point assumes that diameter doesn’t passes through that node
    And third point assumes that diameter passes through that node.

    C++

    class Solution {
    public:
    
        int height(TreeNode *root)
        {
            if(!root) // if node is null
                return 0;
            return max(height(root->left),height(root->right))+1;
        }
    
        int diameterOfBinaryTree(TreeNode* root) {
    
            if(!root)return 0;
        // computing left subtree height and right subtree height at each node
            int lh = height(root->left);
            int rh = height(root->right);
    
            return max(max(diameterOfBinaryTree(root->left),diameterOfBinaryTree(root->right)),lh+rh);
    
        }
    
    };
    

    Complexity Analysis

    • Time complexity : $$O(n^2)$$.

    At each node we are calculating height for left and right subtree
    height() -----> $$O(n)$$
    We are calculating height for each node
    So complexity =$$ O(n*n) = O(n^2)$$

    • Space complexity : $$O(n)$$.

    Approach #2 O(n) [Accepted]

    Storing height at each node
    Intuition

    Here main concern is calculation of height at each node.
    What we can do is to save height calculated so far and use that to calculate height of the parent node. For that we need to return height of child to its parent in recursive call.

    As we are calculating diameter by return statement we can pass a variable by reference so that its value is changed and seen by the calling parent.

    We pass another variable to the function
    dia(node ptr, var height passed by reference )

    Considering base case for leaf nodes : left child and right child are NULL
    Height of left subtree = 0
    Height of right subtree = 0
    As variable is passed by reference
    Left height = 0
    Right height = 0
    So height = 0+0+1 = 1
    As this variable is also passed by reference the parent of leaf node will get its left subtree or right subtree(depending on whether leaf node is left child or right child) height as 1. Same process goes on recursively.

    Intuitively, there are basically two variables which are changing with each call

    1. Diameter calculated till that node so far (by return statement)
    2. Height (by passed by reference variable)

    Finally, logic for diameter is same as above algo i.e. maximum of three quantities

    1. Diameter of left subtree
    2. Diameter of right subtree
    3. Left subtree height + right subtree height

    Visualization

    [Gif Here]

    Test Case
    [4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]
    Output - 8

    [GIF Link]
    http://gph.is/2fTc9FJ

    [alt text](![0_1506392342853_leetcode diameter.gif](Uploading 100%) image url)
    [0_1506620484882_diaporama(1).zip](Uploading 100%)
    [Gif here]

    Solution

    class Solution {
    public:
        int dia(TreeNode * root, int &height)
        {
            int lh=0,rh=0,ld,rd;
            if(!root)
            {
                height=0;
                return 0; // dia = 0
            }
            ld = dia(root->left,lh); // lh passed as a reference
            rd = dia(root->right,rh); // rh passed as a reference
            height = max(lh,rh)+1;
    
            return max(max(ld,rd),lh+rh);
    
        }
        int diameterOfBinaryTree(TreeNode* root) {
            int h=0;
            if(!root)return 0;
            return dia(root,h);
        }
    };
    

    Complexity Analysis

    • Time complexity : $$O(n)$$
      For each node, height is calculated in O(1) and recursion goes for all nodes in the tree. Therefore complexity is O(n).
    • Space complexity : $$O(n)$$.

  • 1

    @minions_ There is a gif here to understand the visualization but while uploading,
    it says not supported. Leetcode team any help would be appreciated to make this editorial better.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.