Height and Diameter of a Tree

Code Snippets in JAVA - pretty much straightforward (This is O(n^2)):

public static int getDiameter(treeNode rootNode)
{
  if (rootNode == null) return 0;
  else
 {
   int rootDiameter = getHeight(goLeft(rootNode)) + getHeight(goRight(rootNode)) + 1;

 int leftDiameter = getDiameter(goLeft(rootNode));



 int rightDiameter =  getDiameter(goRight(rootNode));
 return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
}

}

public static int getHeight (treeNode rootNode)

{
if(rootNode == null) return 0;
else
return Math.max((getHeight(goLeft(rootNode))),(getHeight(goRight(rootNode)))) + 1; 

}

public static treeNode goLeft(treeNode Node)
{
return Node.leftChild;
}

public static treeNode goRight(treeNode Node)
{
return Node.rightChild;
}


public void inOrder(treeNode rootNode)
{
if (rootNode != null)
{
inOrder(goLeft(rootNode));
System.out.print(rootNode.data + ", ");
inOrder(goRight(rootNode));
}


}

Insert Function:

public void insert(treeNode rootElement, int givenData)
{
if (rootElement == null)
{
rootElement = new treeNode(givenData);
         }

else
{
treeNode nodeElement = getParentNode(rootElement, givenData);
if (nodeElement.leftChild == null && givenData < nodeElement.data )
{
nodeElement.leftChild = new treeNode(givenData);

}
else
{
nodeElement.rightChild = new treeNode(givenData);
}

}

}

private treeNode getParentNode(treeNode node, int data)
{
if(data < node.data)
{
if(node.leftChild == null)
{
  return node;
}
else
{
return getParentNode(node.leftChild, data);
}
}
else
{
if(node.rightChild == null)
{
return node;
}
else
{
return getParentNode(node.rightChild, data);
}
}

}




Diameter of a tree

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

Int function:

BinaryTree bst = new BinaryTree();

treeNode root = new treeNode(20);

bst.insert(root, 10);

bst.insert(root, 30);

bst.insert(root, 11);

bst.insert(root, 12);

bst.insert(root, 13);

bst.insert(root, 14);

bst.insert(root, 9);

bst.insert(root, 21);

bst.insert(root, 22);

bst.insert(root, 1);

bst.insert(root, 18);

bst.inOrder(root);

System.out.println("\ntreeHeight : " + getHeight(root));

System.out.println("tree-Diameter : " + getDiameter(root));