0543.md

543. Diameter of Binary Tree

Level:

Topic:

Question

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.

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].

Intuition

Recursive:

1. Get the height of every node's left subtree and right subtree
   • traverse every node
   • add every left and right subtree height until finds the max path
2. Find the longest path

Code

Time: O(n) Space: O(n)

Recursive - Optimised

int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
    longest(root);
    return diameter;
}


private int longest(TreeNode root) {
    if (root == null)
        return 0;

    int leftPath = longest(root.left);
    int rightPath = longest(root.right);
    diameter = Math.max(diameter, leftPath + rightPath);

    return 1 + Math.max(leftPath, rightPath);
}

Time: O(n log n), O(log n) for finding every height
Space: O(n)

Recursive with height:

public int diameterOfBinaryTree(TreeNode root) {
    if (root == null)
        return 0;

    int h = height(root.left) + height(root.right);
    return Math.max(h, Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)));
}


private int height(TreeNode root) {
    if (root == null)
        return 0;
    return 1 + Math.max(height(root.left), height(root.right));
}