CS
Problems Base course RU

Problem

Checking the colours

search tree tree traversal searching in production

A library dumps a red–black tree to disk: for each node, its key, colour and the numbers of its children. After a crash some files may have been corrupted, and before a file is loaded it must be checked. The checks go in this order, and the first violation found is printed:

  1. ORDER: the tree is not a search tree: some node has a key not less than its own in its left subtree, or not greater in its right subtree. Equal keys are a violation too.
  2. ROOT: the root is red.
  3. RED: a red node has a red child.
  4. BLACK: the paths from some node down to the empty links have different numbers of black nodes.

If there are no violations, print OK and the black height: the number of black nodes on any path from the root to an empty link, counting the root. The third and fourth tests are whole trees: the 19,073 earthquakes of the USGS catalogue inserted in time order, and the first 20,000 distinct words of War and Peace; in the other tests the same kind of trees, including one of legost.in page addresses, are damaged in one place. A key is ten times the original key’s rank in sorted order.

Input

The first line holds n and r (1 ≤ n ≤ 10⁵, 1 ≤ r ≤ n): the number of nodes and the number of the root. Then n lines: the i-th holds the key of node i (an integer from 1 to 10⁹), its colour (R or B) and the numbers of its left and right child, 0 if there is no child. It is guaranteed that this is a binary tree with root r containing all n nodes.

Output

One word, ORDER, ROOT, RED or BLACK, or OK and, after a space, the black height.

Examples

Example 1

Input
7 1
40 B 2 3
20 R 4 5
60 R 6 7
10 B 0 0
30 B 0 0
50 B 0 0
70 B 0 0
Output
OK 2

Example 2

Input
5 1
40 B 2 3
20 R 4 5
60 B 0 0
10 B 0 0
30 R 0 0
Output
RED

Limits

Time · Python
4000 ms
Time · Go
1000 ms
Memory
256 MB
Judging
12 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Each rule is checked by one traversal of the tree. But the search rule is about all the keys of a subtree, not just the children: comparing a node with its children is not enough.

2Hint 2

Going down from the root, carry bounds with you: in the left subtree of a node with key k all keys are less than k, in the right subtree greater. The root has no bounds, and each step down narrows one of them. Black heights are easier to compute bottom-up.

3The idea

One top-down traversal with an explicit stack: for each node check that its key is strictly within the bounds passed down from its ancestors, and remember the traversal order. Then the colour of the root, then each red node with its children. Then walk the remembered order backwards, so that children come before parents, and compute the black height: 0 for an empty link, and for a node, the children’s common height plus one if the node is black; if the children’s heights differ, the answer is BLACK.

4Walkthrough

Why bounds are enough. If every node’s key lies strictly between the bounds set by its ancestors, then for any ancestor all the keys of its left subtree are less than its key: on going left from that ancestor the upper bound became its key and after that only decreased. Conversely, if the tree is a search tree, all keys lie within their bounds. So the bounds check is equivalent to the search rule for all subtrees.

The trap is the check “a node is greater than its left child and less than its right one”. In the fifth test, deep in the left half of the tree of the novel’s words, one node’s key has been replaced by a key slightly greater than the root’s. With its parent and children this node is fine: it is a right child and greater than its parent, and it has no right child. But it lies in the root’s left subtree and is greater than the root: a search for this key from the root goes right and does not find it. In the ninth test a key in the tree of site addresses is replaced in the same way, only the new key equals the root’s.

The order of checks is set by the statement, and it is also the order in which repair makes sense: if the key order is broken, it is too early to talk about colours. In the seventh test one red node of the earthquake tree has been repainted black: the order and the neighbours’ colours are fine, but the black heights have diverged. In the eighth a black node under a red parent has turned red: that is both RED and BLACK at once, and the first is printed.

The whole tree of earthquakes inserted in time order has black height 13 and height 26: its right edge alternates black and red nodes, as the article explains.

4+Solution
5Complexity

O(n) time and memory: each node enters the stack once and takes part in the height computation once.

6Common mistakes
  • Comparing only with children. Misses violations several levels apart: the fifth and ninth tests.
  • A non-strict comparison. Equal keys in a search tree are a violation too: a search will find only one of them.
  • Recursion. In the eleventh test the tree is a chain of 50,000 nodes: a recursive traversal in Python hits the depth limit.
  • The black height along one path. Walking the leftmost path and comparing it with the rightmost is not enough: the discrepancy may be in the middle of the tree. Each node must compare its two children.

Algorithms behind it

DS Data structure Red–black tree A search tree with nodes of two colours: height up to 2·log₂(n + 1), at most three rotations per operation. O(log n) for search, insertion and deletion 2 problems DS Data structure Binary search tree Smaller to the left, larger to the right: search, order and the k-th element in the tree's height, from log n to n. O(h): from O(log n) to O(n) 2 problems
The algorithms catalogue