1 Problem Description
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)
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
. Problem Description
We’ll define a “root-to-leaf path” to be a sequence of nodes in a tree starting with the root node and
proceeding downward to a leaf (a node with no children). We’ll say that an empty tree contains no root-
to-leaf paths. So for example, the following tree has exactly four root-to-leaf paths.
Root-to-leaf paths:
Path 1: 5 4 11 7
Path 2: 5 4 11 2
Path 3: 5 8 13
Path 4: 5 8 4 1
Given a sequence of numbers, construct a Binary Search tree T, print out all of its root-to-leaf paths,
one per line.
Input Format:
Sequence of numbers (without repetition), terminated by newline character
Output Format:
Root-to-leaf paths, one per line, from left to right.
Sample Input
10 15 5 7 4 3 12 6 17
Sample Output:
10 5 4 3
10 5 7 6
10 15 12
10 15 17