Diameter of Binary Tree

easy tree dfs

Problem

Given the root of a binary tree, return the length (in edges) of the longest path between any two nodes. The path may or may not pass through the root.

Inputtree = 1,2,3,4,5,null,null (level order)

Output3

DFS returns each subtree's height; at each node, candidate diameter = leftHeight + rightHeight.

tree (level order, 'null' for missing; use small trees)

def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if not node:
            return 0
        lh = height(node.left)
        rh = height(node.right)
        best = max(best, lh + rh)
        return 1 + max(lh, rh)
    height(root)
    return best

function diameter(root) {
  let best = 0;
  function height(node) {
    if (!node) return 0;
    const lh = height(node.left);
    const rh = height(node.right);
    best = Math.max(best, lh + rh);
    return 1 + Math.max(lh, rh);
  }
  height(root);
  return best;
}

class Solution {
    int best = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return best;
    }
    int height(TreeNode node) {
        if (node == null) return 0;
        int lh = height(node.left);
        int rh = height(node.right);
        best = Math.max(best, lh + rh);
        return 1 + Math.max(lh, rh);
    }
}

int best = 0;
int height(TreeNode* node) {
    if (!node) return 0;
    int lh = height(node->left);
    int rh = height(node->right);
    best = max(best, lh + rh);
    return 1 + max(lh, rh);
}
int diameterOfBinaryTree(TreeNode* root) {
    best = 0;
    height(root);
    return best;
}

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