Leetcode: Diameter of a Binary Tree

 This Leetcode question is also in Google, but most commonly on Facebook, Amazon, and Microsoft.  It's a relatively easy question, but absolutely necessary to attempt, if you're gonna try to get a decent representation of binary trees.

The question is as follows:

Given a binary tree, you need to compute the length of the diameter of the tree, which is the longest path between any two nodes of the tree.

The concept is that we recursively call, and look at the maximum between the left and right tree, and take this maximum. In turn we compute we take all of the subtrees here one by one. 

We can compute the left subtree, then right subtree, then take the maximum of these subtrees.

The code is as follows. Shawn Gao did a good job doing this.

public class Solution {

    int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {

        maxDepth(root);

        return max;

    }

    private int maxDepth(TreeNode root) {

        if(root == null) return 0;

        int left = maxDepth(root.left);

        int right = maxDepth(root.right);

        max = Math.max(max, left + right);

        return Math.max(left, right) + 1;

    }

}

Let's try another approach.

One case is including the root, and excluding the root. In a tree graph, we always have the number of nodes = number of edges + 1 because in a tree graph, there are no cycles. The longest path length is what we need too return. We just apply recursion, call the left subtree and the right subtree.

We take the maximum of the left subtree, right subtree, and the left and right subtree path maximum (which, by the way, is another path.).

The following illustration shows the longest path.

And the problem is considering this class: 

  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;

      }

  }

 

and here is the solution: 

public class Solution {

    public int diameterOfBinaryTree(TreeNode root) {

        if(root == null) return 0;

        int dia = depth(root.left + depth(root.right);

        int ldia = diameterOfBinaryTree(root.left);

        int rdia = diameterOfBinaryTree(root.right);

        return Math.max(dia, Math.max(ldia, rdia);

    }

    public int depth(TreeNode root){

        if(root == null) return 0;

        return 1 + Math.max(depth(root.left), depth(root.right));

}