PROBLEM STATEMENT
A binary tree is a tree where each node can have a maximum of two children -
one left child and one right child. You are given an int[] containing numbers
that you must insert into a binary tree that is initially empty. You must
insert the numbers in the order that they appear in that int[] - so before
inserting any number, all previous numbers (those with lower indices) must have
already been inserted. There will be no repeated numbers in the int[]. Each
number n should be inserted as follows (see examples below for step-by-step
examples of node insertions):
- If the tree is empty, n becomes the root node.
- Otherwise, starting at the root node, traverse the tree as follows:
- If n is less than the number at the current node, move to the left child of
the current node - unless the current node has no left child, in which case, n
is inserted as the left child of the current node.
- Otherwise, move to the right child of the current node - unless the current
node has no right child, in which case, n is inserted as the right child of the
current node.
- Repeat until n has been placed in the tree.
Once all the numbers have been placed in the tree, the height of the tree is
simply the length of the longest path from the root node to a leaf node (a node
with no children) - both the root node and leaf node themselves should be
counted as nodes in this path (if the root node IS the leaf node, then the path
length is 1). The resulting tree will be a binary search tree - at any node,
the left subtree will only contain nodes with smaller values than that node,
and the right subtree will only contain nodes with greater values.
DEFINITION
Class: Tree
Parameters: int[]
Returns: int
Method signature (be sure your method is public): int getHeight(int[] numbers);
INPUT CONSTRAINTS
TopCoder will verify that all input constraints are met.
- numbers will contain between 1 and 50 elements inclusive.
- numbers will contain no repeated elements - each element will be distinct.
- each element of numbers will be between -1000000000 and 1000000000 inclusive.
EXAMPLES:
numbers: {3, 2, 5, 4}
Initially, the tree is empty. The first number to insert is 3. Since the tree
is empty, 3 becomes the root node:
3
The next number to insert is 2. 2 is less than 3, and 3 has no left child, so
2 becomes 3's left child:
3
/
2
The next number is 5. 5 is greater than 3, and 3 has no right child, so 5
becomes 3's right child:
3
/ \
2 5
Finally, we insert 4. 4 is greater than 3, so we go to 3's right child (5). 4
is less than 5, and 5 has no left child, so we insert 4 as 5's left child:
3
/ \
2 5
/
4
The height of the tree is 3 since the longest path from the root node to a leaf
node is 3 (the path from 3 to 5 to 4).
Return value: 3
-------------------------------
numbers: {2, 1, 3}
Return value: 2
2
/ \
1 3
-------------------------------
numbers: {7, -2, 9, 3, 10, 22}
Return value: 4
7
/ \
-2 9
\ \
3 10
\
22
-------------------------------