Problem Statement
A binary search tree is a commonly used data structure for storing sorted data. Nodes in a binary search tree may have a left child and/or a right child. As a rule, if some node N has a left child, then the left child and every node in the subtree under the left child must be less than or equal to N. Similarly, if node N has a right child, then the right child and every node in the subtree rooted at the right child must be greater than or equal to N.
Define the depth of the root node to be 0. For any node with depth n, that node's children have depth n+1.
Define the index of the root node to be 1. For any node with index n, that node's left child has index 2n and that node's right child has index 2n+1. For example, the left child of the root node has an index of 2 and the right child has an index of 3. The left child of node 2 is node 4, the right child of node 5 is 11.
Given a
levels[i] represents depth i in the tree.
Each element in levels is represented as follows:
"[node] [node] [node] ...."
There will be 2^d nodes where d is the depth.
Each [node] is separated by a single space.
Each [node] is either an integer or the string "*", representing an empty space in the tree.
The following input matches the tree below {"3","5 9","11 * 4 7"}:
3
/ \
5 9
/ / \
11 4 7
Note that the '*' represents the absence of a right child for the node valued "5".
Definition
- Class:
- BinTree
- Method:
- findBadNode
- Parameters:
- String[]
- Returns:
- int
- Method signature:
- int findBadNode(String[] levels)
- (be sure your method is public)
Notes
- Given a node N on the tree, N is an incorrect node if one or more of the following is true:N is on some left subtree and is greater than the subtree's parent (See examples).N is on a right subtree and is less than the subtree's parentN is an integer and its parent is "*"
- A completely empty tree is valid.
- It is ok for an empty node to have children as long as all of the children are also empty nodes.
Constraints
- Each element of levels will have the correct number of single-space delimited nodes (no leading or trailing spaced allowed).
- Each node will either be "*" or an integer between -100 and 100, inclusive.
- Each element of levels will contain between 1 and 50 characters, inclusive.
Examples
{"10","5 15","2 7 11 17"}
Returns: -1
This is a perfectly fine tree.
{"10","5 *","2 7 * 20"}
Returns: 7
The node valued "20" has an empty node for a parent, which is not allowed.
{"20","-10 30","-20 0 50 70"}
Returns: 6
The node valued "50" is the left child of the node valued "30", so the bad node is index 6 because 50 > 30 and node "50" is in index 6.
{"*"}
Returns: -1
Empty trees are allowed.
{"0","-30 60","-50 1 20 80"}
Returns: 5
In this case, the node valued "1" is larger than the node valued "0", yet "1" is on the left subtree of "0". Since "1" has index 5, return 5.
{"0","-30 60","-50 -20 20 80","-70 -49 -29 -1 0 20 80 80"}
Returns: -1
This tree is ok. Note that it is ok for nodes of equal value to be placed on either subtree of some node.
{"0","-30 60","-50 -20 20 80","-70 -49 -29 -1 -1 20 80 80"}
Returns: 12
This time the node at index 1 is valued "0" and the node at index 12 has a value of "-1" and is on the right subtree of node "0".
{"0","-30 60","-50 -20 20 80","-70 -49 -29 -1 5 20 50 80"}
Returns: 14
{"0","-30 60","-50 -20 -1 80","10 -49 -29 -1 5 20 80 80"}
Returns: 6
{"80","50 60","-50 -20 -1 80","10 -49 -29 -1 5 20 80 80"}
Returns: 3
{"80","90 60","-50 -20 -1 80","10 -49 -29 -1 5 20 80 80"}
Returns: 2
{"0","1 1"}
Returns: 2
{"0","-1 -1"}
Returns: 3
{"0","0 0","-1 -1 -1 -1"}
Returns: 5
Although the last three "-1" valued nodes are all incorrect, the smallest index must be returned, so return 5. Note that the "-1" node at index 4 does not cause any rule violations.
{"3","5 9","11 * 4 7"}
Returns: 2
The first incorrect node is index 2, because 5 > 3.
{"*","* *","* * * *","* * * * * * * *"}
Returns: -1
Empty tree are ok, even if the other depths are not necessary.
{"*","* *","* * * *","* * * * 0 * * *"}
Returns: 12
There is a node whose parent is an empty node, violating the rules.
{ "0", "-30 60", "-50 1 20 80" }
Returns: 5
{ "5", "6 6", "7 7 7 7", "8 8 8 8 8 8 8 8" }
Returns: 2
{ "5", "0 *" }
Returns: -1
{ "0", "-10 10", "-20 50 5 50" }
Returns: 5