CareerCup

BFS Search with track of count on each iteration, the biggest value is answer.
Solition is O(n)

Does not the postorder traversal solve the problem and it would be O(n) ?

There are three cases to consider when trying to find the longest path between two nodes in a binary tree (diameter):

The longest path passes through the root,
The longest path is entirely contained in the left sub-tree,
The longest path is entirely contained in the right sub-tree.
The longest path through the root is simply the sum of the heights of the left and right sub-trees + 1 (for the root node), and the other two can be found recursively:

public static int getDiameter(BinaryTreeNode root) {        
    if (root == null)
        return 0;

    int rootDiameter = getHeight(root.getLeft()) + getHeight(root.getRight()) + 1;
    int leftDiameter = getDiameter(root.getLeft());
    int rightDiameter = getDiameter(root.getRight());

    return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
}

public static int getHeight(BinaryTreeNode root) {
    if (root == null)
        return 0;

    return Math.max(getHeight(root.getLeft()), getHeight(root.getRight())) + 1;
}

2 methods to find diameter in O(n)

1. use hashing: store height of every node in hash table -> O(2n)

map <node*,int> h;
int height(struct node* node)
{
if(node == NULL)
return 0;
	int a=height(node->left);
	int b=height(node->right);
h[node]= 1 + max(a,b);
return h[node];
}

int diameter(struct node * tree)
{
if (tree == 0)
return 0;
int lheight = h[tree->left];
int rheight = h[tree->right];
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}

2. use postorder traversal in height fuction and keep updating value of diameter to leftheight + rightheight +1 -> O(n)

int dia(node* root,int *d){
	int lheight, rheight;
	if(!root) return 0;
	lheight=dia(root->left,d);
	rheight=dia(root->right,d);
	if(lheight+rheight+1>*d) *d=lheight+rheight+1;
	return 1+ max(lheight,rheight);
}

int diameter(node* root){
	int d=0;
	dia(root,&d);
	return d;
}

This can be solved in O(n) with one traversal

public class Solution {
    private int res=0;
    private int helper(TreeNode root) {
        if(root==null){
            return -1;
        }
        int l=1+helper(root.left);
        int r=1+helper(root.right);
        res=Math.max(res,l+r);
        return Math.max(l,r);
    }
    public int diameterOfBinaryTree(TreeNode root){
        if(root==null)  return 0;
        helper(root);
        return res;
    }
}

Write a recursive solution,
int diameter(Node *n)
{
if(n==NULL) return 0;
else return max( diameter(n->left), diameter(n->right), height(n->left) + height(n->right) + 1);
}