401606: GYM100499 E Binary Search Tree

A binary tree is a tree data structure where each node has at most two children which are referred to as left child and right child. A binary search tree is a binary tree where each node has a comparable key and must satisfy the following conditions:

• The left sub-tree of a node contains only nodes with keys less than the node’s key.
• The right sub-tree of a node contains only nodes with keys more than the node’s key.
• The left and the right sub-tree are also binary search tree.

Given a binary tree, your task is to choose a maximal set S of connected nodes in the given tree so that these nodes and the relations (left child, right child, or ancestor) among them form a binary search tree.

The first line of input is the number T (T ≤ 20).

Then T tests follow:

• The first line of each test is the number N (1 ≤ N ≤ 10⁵) - the number of node of the given binary tree
• Then N lines follow. The ith line describes node numbered i (nodes are numbered 1 to N). Each node is described by 3 integers: the index of its left child, the index of its right child, and the comparable key in that node. The value of a key will not exceed 10⁶. If a node doesn’t have a left child and/or a right child, they will be represented as 0. The root node is numbered 1.

For each test, print the maximal size of S.

2
8
2 3 10
4 5 5
6 7 15
0 0 3
0 0 7
0 0 17
0 8 13
0 0 14
3
0 2 5
0 3 6
0 0 7

5
3

The example test case correspond to the following figure: