The diameter of a binary tree [No. 40]

Definition: The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.

The diameter of a tree T is the largest of the following quantities:

• the diameter of T's left subtree
• the diameter of T's right subtree
• the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)

 /* Function to get diameter of a binary tree */
    static int diameter(Node root) {
    	if (root == null) {
    		return 0;
    	}
    	
    	int lHeight = height(root.leftChild);
    	int rHeight = height(root.rightChild);
    	
    	int lDiameter = diameter(root.leftChild);
    	int rDiameter = diameter(root.rightChild);
    	
    	return max(lHeight + rHeight + 1, max(lDiameter, rDiameter));
    	
    }
    
    /*  The function Compute the "height" of a tree. Height is the
    number f nodes along the longest path from the root node
    down to the farthest leaf node.*/
    static int  height(Node root) {
    	if (root == null) {
    		return 0;
    	}
    	
    	return 1 + max(height(root.leftChild), height(root.rightChild));
    }

The complexity of the program is O(n^2), because the height function of called everytime when we go through the tree.

There is another solution and the complexity is O(N). The main idea of this approach is that the node stores its left child's and right child's maximum diameter if the node's child is the "root", therefore, there is no need to recursively call the height method. The drawback is we need to add two extra variables in the node class.

int findMaxLen(Node root) {
	 
	int nMaxLen = 0;
	if (root == null) return 0;
	
	if (root.leftChild == null) {
		root.nMaxLeft = 0;
	}
	
	if (root.rightChild == null) {
		root.nMaxRight = 0;
	}
	
	if (root.leftChild != null) {
		findMaxLen(root.leftChild);
	}
	
	if (root.rightChild != null) {
		findMaxLen(root.rightChild);
	}
	
	if (root.leftChild != null) {
		int nTempMaxLen = 0;
		nTempMaxLen = (root.leftChild.nMaxLeft > root.leftChild.nMaxRight) ? 
			root.leftChild.nMaxLeft : root.leftChild.nMaxRight;
		root.nMaxLeft = nTempMaxLen + 1;
	}
	
	if (root.rightChild != null) {
		int nTempMaxLen = 0;
		nTempMaxLen = (root.rightChild.nMaxLeft > root.rightChild.nMaxRight) ? 
			root.rightChild.nMaxLeft : root.rightChild.nMaxRight;
		root.nMaxRight = nTempMaxLen + 1;
	}
	
	if (root.nMaxLeft + root.nMaxRight > nMaxLen) {
		nMaxLen = root.nMaxLeft + root.nMaxRight;
	}
	
	return nMaxLen;
}

参考：编程之美