Detect if nodes on a tree are directly connected

Question

There is a tree that looks like this:

User can select multiple nodes from a tree. I want to detect whether the selected nodes are directly connected. How to achieve that?

Here are some examples with a good selection:

and here are examples with a bad selection:

Here is the JSON data that I'm using

const tree = {
  id: "A",
  children: [
    {
      id: "B",
      children: [
        {
          id: "D",
          children: [
            {
              id: "E",
              children: [],
            },
          ],
        },
      ],
    },
    {
      id: "C",
      children: [],
    },
  ],
};

Answer 1

We could distinguish these states that a tree could have with respect to the question:

• Clear: It has no selected node.
• Ongoing: It has a valid selection, and the root is part of it (so it could be extended in upward direction when this tree is a subtree of a larger tree).
• Completed: It has a valid selection, and the root is not part of it.
• Bad: It has an invalid selection.
• One: The root is selected, but information about the tree is not yet complete (temporary state).

We can derive this state from recursion, by doing a post-order traversal. So we would first determine the state of the child subtrees, and only then use that info for determining the (current) root's state. During the collection of states of the children, there can be a condition which immediately determines the root's state as "bad", and so recursion should immediately unwind.

Here is an implementation:

"use strict";

const STATES = { CLEAR: 0, ONGOING: 1, COMPLETE: 2, BAD: 3, ONE: 4 };

function isPath(tree, selected) {
    let selectedSet = new Set(selected);
    
    function dfs(node) {
        let state = selectedSet.has(node.id) ? STATES.ONE : STATES.CLEAR;
        for (const child of node.children) {
            const childState = dfs(child);
            if (childState == STATES.CLEAR) continue;
            if (childState == STATES.BAD
                  || childState == STATES.COMPLETE && state != STATES.CLEAR
                  || childState == STATES.ONGOING && state == STATES.COMPLETE) return STATES.BAD;
            state = state == STATES.ONE ? STATES.ONGOING : STATES.COMPLETE;
        }
        return state == STATES.ONE ? STATES.ONGOING : state;
    }
    
    return [STATES.ONGOING, STATES.COMPLETE].includes(dfs(tree)) 
}

// Example run
const tree = {id: "A",children: [{id: "B",children: [{id: "D",children: [{id: "E",children: [],},],},],},{id: "C",children: [],},],};

console.log(isPath(tree, ["E","A"])); // false
console.log(isPath(tree, ["B","D"])); // true
console.log(isPath(tree, ["E"])); // true
console.log(isPath(tree, ["C","E"])); // false
console.log(isPath(tree, ["C","A","B"])); // true