Data Structures:

The Left-Child Right-Sibling tree (LC-RS) is a kind of binary tree that can be used to represent general trees, which have an arbitrary number of children per node. For example, the general tree on the left below can be converted to its equivalent LC-RS tree on the right:

 General Tree LC-RS Equivalent LC-RS Rearranged as a Binary Tree 1 1 1 /|\ / / / | \ / 2 / | \ / / \ 2 3 4 2---3---4 5 3 / \ | / / \ \ 5 6 7 5---6 7 6 4 / \ / / 8 9 8---9 7 / 8 \ 9 

Implement the generic convertTrinary2LCRS method below so that it converts a given tree into an LC-RS binary tree. For simplicity, assume the given tree will be a full trinary tree, that is, a tree where every parent has exactly three children and all leaves are at the same level.

public static  BinaryTreenode convertTrinary2LCRS(TrinaryTreenode triTreeRoot) { //TODO: COMPLETE THIS METHOD } 

The method is passed a reference to a TrinaryTreenode that is the root of the tree to be converted, and it returns a reference to the root of a BinaryTreenode that is the equivalent LC-RS tree.

The TrinaryTreenode class is implemented as shown below:

class TrinaryTreenode  { // *** fields *** private K key; private TrinaryTreenode leftChild; private TrinaryTreenode midChild; private TrinaryTreenode rightChild; // *** methods *** public K getKey() { return key; } public TrinaryTreenode getLeft() { return leftChild; } public TrinaryTreenode getMid() { return midChild; } public TrinaryTreenode getRight() { return rightChild; } } 

Assume the BinaryTreenode class is done similarly but without the midChild field and accessor method, and with this constructor and these mutator methods:

public BinaryTreenode(K keyRef, BinaryTreeNode leftNodeRef, BinaryTreeNode rightNodeRef) { key = keyRef; leftChild = leftNodeRef; rightChild = rightNodeRef; } public void setLeft(BinaryTreeNode leftNodeRef) { leftChild = leftNodeRef; } public void setRight(BinaryTreeNode rightNodeRef) { rightChild = rightNodeRef; }