Kata

If you wish to use the LCA in your solution, I suggest you solve Find the Lowest Common Ancestor first.

"Given a node from a Tree, return the transition execution sequence required to activate this node."

Input

node: the node requested to be active

Output

Return the transition execution sequence required to activate this node, as an array of array of 2 elements, with the first element being the name of a node, and the second a flag indicating whether the node corresponding to that name got activated 1 or deactivated 0. Return an empty array if the node is already active.

The following rules are at all time present and are applied recursively to related nodes. All trees in this kata are valid.

1. Any node that is active, must have an active parent, except for the root note, which has no parent.
2. Any node that is inactive, cannot have any active children. (equivalent of rule #1, but from different perspective)
3. Any active node that has children, can have at most 1 active child.

The transition execution sequence consists of the nodes that have their status changed, in order of execution. We always start with a given node for which we request the status to get activated. Keeping the rules in mind, we can come up with the following behavior:

1. Any node that requests to get activated, but which is active, should do nothing.
2. Any node that requests to get activated, and is inactive, should first let the parent request to get activated, before changing its own status to active.
3. Any node that requests to get activated, if any sibling is still active, should let that sibling request to get deactivated first.
4. Any node that requests to get deactivated, but which is not active, should do nothing.
5. Any node that requests to get deactivated, and is active, should first let any active child request to get deactivated, before changing its own status to inactive.

Note that since the tree must be valid at any step in the activations / deactivations, this will constrain the order of the output array. You should be able to figure out the correct order of steps from the above rules and behaviors.

Tree

A tree represents a hierarchical tree structure with a set of connected nodes. In this kata, there is no specific data structure for a tree. The root node (topmost node) will act as the tree.

Node

Each node in the tree can be connected to zero, one or more children, but must be connected to exactly one parent, except for the root node, which has no parent. In this kata, a node is connected to its parent using property up, its siblings using properties left and right, and its first child using property down. To get all children, call down and keep calling right until reaching a null pointer. Each node will also have a unique name (lowercase letters and/or numbers) and a flag indicating its status ( active = 1, inactive = 0 ).

Tree Depiction

In this kata, a tree gets displayed as follows. The root node at the top, forking out to its children, and further to grandchildren and other successors. The name, although always consisting of lowercase letters and numbers, will be shown in lowercase for inactive nodes and uppercase for active nodes in all examples used in this kata. In the examples below, the following nodes are active in the left tree: a -> aa -> aab, and the following in the right tree: a -> ab.

             A                                A
             |                                |
       AA ---+--- ab                    +-----+-----+
       |          |                     |     |     |
aaa ---+--- AAB   |                     aa    AB    ac
                  |                           |
           aba ---+--- abb             aba ---+--- abb

The reference solution is able to solve all test cases in +-1 second, so I don't expect too much problems with user solutions timing out. The following random tests are provided:

● 50 random tests with 1 <= depth <= 5 and 2 <= breadth <= 4
● 5 random tests with 3 <= depth <= 8 and 1 <= breadth <= 10
● 5 random tests with 10 <= depth <= 13 and 1 <= breadth <= 2

You can callconsole.dir(printTree(node), {depth: null}) to inspect a node. Calling this on the root node renders the entire tree. For bigger trees, you may want to use an IDE to inspect the object.

Examples: Valid Trees

Example Tree

A tree with an active node all the way through the descendants of the root up to reaching a leaf node a -> aa -> aab.

             A
             |
       AA ---+--- ab
       |          |
aaa ---+--- AAB   |
                  |
           aba ---+--- abb       

Example Tree

A tree with an active node through the descendants of the root up to an internal node a -> aa.

             A
             |
       AA ---+--- ab
       |          |
aaa ---+--- aab   |
                  |
           aba ---+--- abb       

Example Tree

A tree with no active nodes.

             a
             |
       aa ---+--- ab
       |          |
aaa ---+--- aab   |
                  |
           aba ---+--- abb       

Examples: Invalid Trees

Example Tree breaking rules #1 and #2

1. aa and aab can not be active, because their predecessor a is inactive.
2. a cannot be inactive, because its successors aa and aab are active.

             a
             |
       AA ---+--- ab
       |          |
aaa ---+--- AAB   |
                  |
           aba ---+--- abb       

Example Tree breaking rule #3

3. aa or ab can be active, but not both.

             A
             |
       AA ---+--- AB
       |          |
aaa ---+--- AAB   |
                  |
           ABA ---+--- abb       

The following examples are all available in the sample tests. They should give a good idea about the expected behavior for more complex trees.

(*) is used to show which node we want to activate

Example: Node already active

request activation(aa)      = []              // node aa is already active

              A
              |
       *AA ---+--- ab
        |          |
 aaa ---+--- AAB   |
                   |
            aba ---+--- abb       

Example: Parent active

request activation(aaa)     = [               
                                ["aaa",1]     // aaa gets activated
                              ]

              A
              |
        AA ---+--- ab
        |          |
*aaa ---+--- aab   |
                   |
            aba ---+--- abb       

Example: No active node yet

request activation(aaa)     = [               
                                ["a",1],      // root a needs to be activated first
                                ["aa",1],     // parent aa needs to be activated after
                                ["aaa",1]     // aaa is activated
                              ]

              a
              |
        aa ---+--- ab
        |          |
*aaa ---+--- aab   |
                   |
            aba ---+--- abb       

Example: Sibling active

request activation(aaa)     = [               
                                ["aab",0],    // sibling aab needs to be deactivated first
                                ["aaa",1]     // node aaa gets activated
                              ]

              A
              |
        AA ---+--- ab
        |          |
*aaa ---+--- AAB   |
                   |
            aba ---+--- abb       

Example: Uncle active

request activation(aaa)     = [               
                                ["ab",0],     // uncle ab needs to be deactivated first
                                ["aa",1],     // parent aa needs to be activated after
                                ["aaa",1]     // node aaa gets activated
                              ]

              A
              |
        aa ---+--- AB
        |          |
*aaa  ---+--- aab  |
                   |
            aba ---+--- abb       

Example: Cousin active

request activation(aaa)     = [               
                                ["abb",0],    // cousin abb needs to be deactivated first
                                ["ab",0],     // uncle ab needs to be deactivated after
                                ["aa",1],     // parent aa needs to be activated after
                                ["aaa",1]     // node aaa gets activated
                              ]

              A
              |
        aa ---+--- AB
        |          |
*aaa ---+--- aab   |
                   |
            aba ---+--- ABB       

Example: Nephew active

request activation(aa)      = [               
                                ["abb",0],    // nephew abb needs to be deactivated first
                                ["ab",0],     // sibling ab needs to be deactivated after
                                ["aa",1]      // node aa gets activated
                              ]

             A
             |
      *aa ---+--- AB
       |          |
aaa ---+--- aab   |
                  |
           aba ---+--- ABB       

● root node: a node with no parent, representing a tree
● internal node: a node with a parent and at least one child
● leaf node: a node without any children
● ancestors: the node self and any ancestor of the parent
● predecessors: the parent node and any predecessor of the parent
● descendants: the node self and any descendant of the children
● successors: the children and any successor of the children