543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of thelongestpath between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

          1
         / \
        2   3
       / \     
      4   5

Return3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note:The length of path between two nodes is represented by the number of edges between them.

Analysis:

Use bubble up approach to keep calculating max height for each node. At each node, we also add left and right branch height together and update max diameter accordingly. This way, when whole tree is traversed, we are done.

Complexity:

Time: O(N)

Space: O(logn)

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null)
        {
            return 0;
        }

        traverse(root);
        return max-1;
    }

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

}