You are given a binary tree in parent child configuration format.

The tree may not be a complete binary tree.

Your task is to choose a largest possible complete binary tree from the given tree by trimming away nodes that are not part of the chosen complete tree.

A complete binary tree is a binary tree where every level except possibly the last level is completely filled, and all nodes in the last level are placed as far left as possible.

The chosen complete tree must preserve the original parent child relationships and left right child positions from the given tree.

You are not allowed to move nodes, reorder nodes, or fill missing positions by shifting nodes from another place in the tree.

Every node that is not part of the chosen complete tree is considered removed and belongs to the trash queue.

CompleteBinaryTreeTrimmer(List<String> nodeConfigs)

• Initializes the object using the given binary tree configuration.
• nodeConfigs represents the binary tree using parent child configuration.
• Each string in nodeConfigs has the format "nodeId,parentId,childSide".
• nodeId is the unique integer id of the current node.
• parentId is the unique integer id of the parent node.
• The original root node has no parent, so its parentId is -1.
• childSide is one of "ROOT", "L", or "R".
• "ROOT" is used only for the original root node.
• "L" means the current node is the left child of its parent.
• "R" means the current node is the right child of its parent.
• The constructor parameter itself will never be null.
• The input list will never contain null values.

List<String> getCompleteTreeLevels()

• Returns the chosen complete tree level by level.
• Each string represents one level of the chosen complete tree.
• Node ids inside one level must be comma separated.
• Node ids inside one level must be ordered from left to right.
• Every returned level string must contain at least one node id.
• If the chosen complete tree has no nodes, return an empty List<String>.

List<Integer> getTrashNodeIds()

• Returns the node ids that are not part of the chosen complete tree.
• The returned node ids must be sorted in ascending order.
• If no node is removed, return an empty List<Integer>.

The tree is passed only once in the constructor as a List<String>.

Each string contains exactly three comma-separated values:

"nodeId,parentId,childSide"

For example:

List.of("1,-1,ROOT", "2,1,L", "3,1,R", "4,2,L", "5,2,R", "7,3,R")

represents a tree where:

1 is the original root.
2 is the left child of 1.
3 is the right child of 1.
4 is the left child of 2.
5 is the right child of 2.
7 is the right child of 3.

Since there is no record for the left child of node 3, that child position is considered missing.

The final complete tree may be rooted at any node from the original tree.

If a node is selected as the root of the final complete tree, then only nodes inside that selected node's original subtree can be part of the final complete tree.

The final complete tree must preserve original child directions.

If a node was originally a left child, it can only remain as a left child of the same parent when both are kept.

If a node was originally a right child, it can only remain as a right child of the same parent when both are kept.

You cannot move a node from right to left, from left to right, or under a different parent.

A node can be part of the chosen complete tree only if every earlier position in level order inside that chosen tree also exists and is kept.

Among all possible complete trees that can be formed by trimming nodes, choose the one with the maximum number of nodes.

If multiple complete trees have the same maximum number of nodes, compare their full level-order traversal from left to right.

Return the complete tree whose traversal has the smaller node id at the first position where the two traversals differ.

Every original node that is not part of the chosen complete tree is considered removed.

The method getTrashNodeIds() must return all removed node ids sorted in ascending order.

The returned trash list is sorted by node id, not by removal time.

The method getCompleteTreeLevels() returns the chosen complete tree level by level.

For example, if the chosen complete tree has level order traversal:

1, 2, 3, 4, 5

then the returned list must be:

List.of("1", "2,3", "4,5")

The method getTrashNodeIds() returns sorted removed node ids.

For example:

List.of(7, 9, 12)

• 0 ≤ nodeConfigs.size() ≤ 105
• Each string in nodeConfigs has the format "nodeId,parentId,childSide".
• -1 ≤ parentId ≤ 109
• 0 ≤ nodeId ≤ 109
• All nodeId values are unique.
• If nodeConfigs is not empty, there is exactly one original root node.
• The original root node has parentId = -1 and childSide = "ROOT".
• Every non-root node has childSide = "L" or childSide = "R".
• Every non-root node has a parent that exists in nodeConfigs.
• No parent has more than one left child.
• No parent has more than one right child.
• The given configuration always represents a valid binary tree.
• The constructor input list itself is never null.
• The constructor input list never contains null values.
• The methods can be called multiple times and must return the same result every time.

CompleteBinaryTreeTrimmer trimmer = new CompleteBinaryTreeTrimmer(nodeConfigs = List.of("1,-1,ROOT", "2,1,L", "3,1,R", "4,2,L", "5,2,R", "7,3,R"))

trimmer.getCompleteTreeLevels()

returns

List.of("1", "2,3", "4,5")

trimmer.getTrashNodeIds()

returns

List.of(7)

Explanation:

The largest complete tree is rooted at node 1 and contains nodes 1, 2, 3, 4, 5. Node 3 has no left child, so node 7 cannot be kept as the right child of node 3 in a complete tree. Therefore, node 7 is removed.

CompleteBinaryTreeTrimmer trimmer = new CompleteBinaryTreeTrimmer(nodeConfigs = List.of("1,-1,ROOT", "2,1,L", "3,1,R", "5,2,R", "6,3,L", "7,3,R"))

trimmer.getCompleteTreeLevels()

returns

List.of("1", "2,3")

trimmer.getTrashNodeIds()

returns

List.of(5,6,7)

Explanation:

One possible complete tree is rooted at node 1 and contains nodes 1, 2, 3. Another possible complete tree is rooted at node 3 and contains nodes 3, 6, 7. Both have 3 nodes. Their level-order traversals are 1,2,3 and 3,6,7. Since 1 is smaller than 3 at the first differing position, the complete tree rooted at node 1 is chosen.

CompleteBinaryTreeTrimmer trimmer = new CompleteBinaryTreeTrimmer(nodeConfigs = List.of("10,-1,ROOT", "20,10,R", "1,20,L", "2,20,R"))

trimmer.getCompleteTreeLevels()

returns

List.of("20", "1,2")

trimmer.getTrashNodeIds()

returns

List.of(10)

Explanation:

The tree rooted at node 10 cannot keep node 20 as its right child without a left child. So the largest complete tree rooted at node 10 has only node 10. However, the complete tree rooted at node 20 has nodes 20, 1, 2. Since it is larger, it is chosen.

CompleteBinaryTreeTrimmer trimmer = new CompleteBinaryTreeTrimmer(nodeConfigs = List.of("50,-1,ROOT", "20,50,L", "10,20,L"))

trimmer.getCompleteTreeLevels()

returns

List.of("20", "10")

trimmer.getTrashNodeIds()

returns

List.of(50)

Explanation:

The complete tree rooted at node 50 can contain nodes 50, 20. The complete tree rooted at node 20 can contain nodes 20, 10. Both complete trees have 2 nodes. Their level-order traversals are 50,20 and 20,10. Since 20 is smaller than 50 at the first differing position, the complete tree rooted at node 20 is chosen.

CompleteBinaryTreeTrimmer trimmer = new CompleteBinaryTreeTrimmer(nodeConfigs = List.of("1,-1,ROOT", "2,1,L", "3,1,R", "4,2,L", "5,2,R", "6,3,L", "7,3,R"))

trimmer.getCompleteTreeLevels()

returns

List.of("1", "2,3", "4,5,6,7")

trimmer.getTrashNodeIds()

returns

List.of()

Explanation:

The whole given tree is already a complete binary tree. Therefore, the chosen complete tree contains all nodes and the trash queue is empty.

CompleteBinaryTreeTrimmer trimmer = new CompleteBinaryTreeTrimmer(nodeConfigs = List.of())

trimmer.getCompleteTreeLevels()

returns

List.of()

trimmer.getTrashNodeIds()

returns

List.of()

Explanation:

The original tree has no nodes. Therefore, there is no complete tree and no trash node.