_543. Diameter of Binary Tree.md

543. Diameter of Binary Tree

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 03, 2024

Last updated : July 01, 2024

---

Related Topics : Tree, Depth-First Search, Binary Tree

Acceptance Rate : 61.69 %

---

Solutions

• e543 v2.java
• e543.java
• e543.c
• e543.py

Java

e543 v2.java

// Beats 100% 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int diam = Integer.MIN_VALUE;
    public int diameterOfBinaryTree(TreeNode root) {
        helper(root);
        return diam;
    }

    public int helper(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftData = helper(node.left);
        int rightData = helper(node.right);

        if (diam <= leftData + rightData) {
            diam = leftData + rightData;
        }

        return Integer.max(leftData, rightData) + 1;
    }

    
}

e543.java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        return helper(root)[1] - 1;
    }

    public int[] helper(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }

        int[] leftData = helper(node.left);
        int[] rightData = helper(node.right);

        return new int[]{Integer.max(leftData[0], rightData[0]) + 1,
                         Integer.max(Integer.max(leftData[1], rightData[1]), leftData[0] + rightData[0] + 1)};

    }

    
}

C

e543.c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int findHeight(struct TreeNode* node, int* diam) {
    if (!node) {
        return 0;
    }

    int hLeft = findHeight(node->left, diam);
    int hRight = findHeight(node->right, diam);

    if (hLeft + hRight > *diam) {
        *diam = hLeft + hRight;
    }

    return (((hLeft > hRight) ? hLeft : hRight) + 1);
} 

int diameterOfBinaryTree(struct TreeNode* root) {
    int* temp = (int*) malloc(sizeof(int));
    findHeight(root, temp);
    return *temp;
    free(temp);
}

Python

e543.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:

        # Return height but compare current diameter to maxCase
        # [height, maxDiameter]
        def maxCaseAndHeight(node: Optional[TreeNode]):
            if not node :
                return (0, 0)
            
            leftData = maxCaseAndHeight(node.left)
            rightData = maxCaseAndHeight(node.right)

            return (max(leftData[0], rightData[0]) + 1, # height
                    max(leftData[0] + rightData[0] + 1, # max diameter
                        leftData[1], 
                        rightData[1])
                    )

        # -1 cause PathNodes = PathEdges + 1
        return maxCaseAndHeight(root)[1] - 1