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.