## Binary Search Tree ( Finding the height and diameter of a BST )

Passing over to Binary Search Tree , this one is an easy problem .

One should have a basic knowledge about BST and also know how to insert data into it . i am really not sure of whether it is a standard for BST or not but here i am going to use LDR to insert data in the tree , i.e ( if the value to be inserted is smaller than root it goes to left and if it is greater then it goes to right ) . Ok without taking much time i discuss the problem with u .

Problem :

The diameter of a tree 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)

The Fig below shows a tree with diameter nine, the leaves that form the ends of a

longest path are shaded (note that there is more than one path in the tree of length nine, but no path

longer than nine nodes).

Input Format:

Sequence of Numbers(without repetition), terminated by newline character.

Output Format:

Height of tree T. Diameter of tree T.

Sample Input

10 15 5 7 4 3 12 6 17

Sample Output:

3

6

One should have a basic knowledge about BST and also know how to insert data into it . i am really not sure of whether it is a standard for BST or not but here i am going to use LDR to insert data in the tree , i.e ( if the value to be inserted is smaller than root it goes to left and if it is greater then it goes to right ) . Ok without taking much time i discuss the problem with u .

Problem :

The diameter of a tree 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)

The Fig below shows a tree with diameter nine, the leaves that form the ends of a

longest path are shaded (note that there is more than one path in the tree of length nine, but no path

longer than nine nodes).

Input Format:

Sequence of Numbers(without repetition), terminated by newline character.

Output Format:

Height of tree T. Diameter of tree T.

Sample Input

10 15 5 7 4 3 12 6 17

Sample Output:

3

6

Solution:

The diameter of a tree is clearly explained in the question , the diameter of a tree can be entirely on the left hand side of the root , it can be entirely on the right side or it can stretch from left leaf node to the right leaf node , actually its the longest of these three , and height is the

( no. of nodes in the longest path - 1 ) and the longest path here stands for the path from root to the leaf node.

so here i am giving a recursive code to find the height of the tree and also the diameter of tree , and this code is written for taking the inputs till EOF also since the test cases can be very large there is a separate function to FREE the nodes after each test case.