Today I brought a classic node problem not to demonstrate how I solved the problem, but simply because I thought the solution to this problem includes a variety of JavaScript Syntax.

Tree Constructor

Have the function TreeConstructor(strArr) take the array of strings stored in strArr, which will contain pairs of integers in the following format: (i1,i2), where i1 represents a child node in a tree and the second integer i2 signifies that it is the parent of i1. For example: if strArr is ["(1,2)", "(2,4)", "(7,2)"], then this forms the following tree: (picture above)
which you can see forms a proper binary tree. Your program should, in this case, return the string true because a valid binary tree can be formed. If a proper binary tree cannot be formed with the integer pairs, then return the string false. All of the integers within the tree will be unique, which means there can only be one node in the tree with the given integer value.

Input: ["(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"] -> Output: true
Input: ["(1,2)", "(3,2)", "(2,12)", "(5,2)"] -> Output: false

To solve this,

(This is how I solved it, but normally this problem includes one more step, so I highly suggest you look it up; just Google Tree Constructor.)

1. Check if there are any parents that are repeated.
2. Check if there is one or two children for each parent and no more.
3. Check if it’s a cycle.

But before we move on to solving the actual problem, we’re first going to look into the syntax we’ll be using in this post.

JavaScript Syntax

A quick refresher on the JavaScript pieces used below, before diving into the problem.

reduce (building an object)

reduce walks through an array and builds up a single value.

It doesn't have to be a number, it can be an object too.

const arr = ["(1,2)", "(2,4)"];

const obj = arr.reduce((acc, str) => {
  acc[str] = true;
  return acc;
}, {}); // {} is the starting value (accumulator)

slice

Cuts out part of a string (or array) by index, without changing the original.

"(1,2)".slice(1, -1); // "1,2"  (removes first and last character)

map(Number)

map transforms every item in an array. Passing Number directly converts each item to a number. (no need to write x => Number(x).)

["1", "2"].map(Number); // [1, 2]

split(',')

Breaks a string into an array, cutting at every match of the separator.

"1,2".split(","); // ["1", "2"]

Destructuring

Unpacks values from an array (or object) straight into named variables.

const [child, parent] = [1, 2];
// child = 1, parent = 2

Object.keys, Object.values, Object.entries

Three ways to pull data out of an object.

Keys always come back as strings.

const obj = { 1: 2, 5: 7 };

Object.keys(obj);    // ["1", "5"]
Object.values(obj);  // [2, 7]
Object.entries(obj); // [["1", 2], ["5", 7]]

Set vs Object

A Set stores unique values only, no keys.

Use it when you just need to ask "have I seen this before?"

const visited = new Set();
visited.add(1);
visited.has(1); // true

An Object stores key → value pairs.

Use it when you need to look something up by key.

A modern alternative to Object.keys

Object.hasOwn(obj, key) checks if a key exists directly on an object.

A cleaner alternative to Object.keys(obj).includes(key).

Object.hasOwn({ 1: 2 }, 1); // true

The value in obj pattern

in checks whether a value exists as a key in an object: handy for cycle detection or duplicate checks.

const obj = { 1: 2, 2: 4 };

1 in obj; // true  → 1 is a key
9 in obj; // false → 9 is not a key


while (current in obj) {
  // keep walking up as long as `current` still has a parent
  current = obj[current];
}

Step1. Check if there are any parents that are repeated.

const obj = {};
let hasMoreThanOneParent = false;

for (const str of strArr) {
    const [child, parent] = str.slice(1, -1).split(',').map(Number);

    // A child key appearing twice means this node has two parents
    if (child in obj) hasMoreThanOneParent = true;
    obj[child] = parent;
}

• First, you destructure into [child, parent] pairs, slice it to remove (), split it to turn it into an array, and then turn it into numbers.
  • “(1,2)” → “1,2” → [“1”, “2”] → '[1,2]
• (child in obj)
  • {1:2, 2:4, 5:6, …} → [“1”, “2”, “5”,…]
• if(child in obj) hasMoreThanTwoParent = true
  • If the same child appears as a key more than once, it means that node was already assigned a parent before, so this second assignment gives it two parents.

In pseudo, it should look something like this:

for each "(child, parent)" pair in the input:
  if child already exists as a key in obj:
    mark hasMoreThanOneParent = true
  store obj[child] = parent

Step2. Check if there is one or two children for each parent and no more.

  let hasMoreThanTwoChildren = false;
  
  for (const str of strArr) {
    const [child, parent] = str.slice(1,-1).split(',').map(Number);

    // Count how many children each parent has
    childrenCount[parent] = (childrenCount[parent] || 0) + 1;
    if (childrenCount[parent] > 2) hasMoreThanTwoChildren = true;
  }

• (childrenCount[parent] || 0) for the first run - default value

Step3. Check if it’s a cycle.

// Walk up from every node to check for cycles
  let isCycle = false;
  for (const start of Object.keys(obj)) {
    const visited = new Set();
    let current = Number(start);

    while (current in obj) {
      if (visited.has(current)) { isCycle = true; break; } // already visited -> cycle
      visited.add(current);
      current = obj[current];
    }
    if (isCycle) break;
  }

This part gets a little more confusing.

It’s better to understand this in pseudo.

for each node in obj:
    create an empty visited set
    start walking from this node

    while the current node has a parent (exists as a key in obj):
        if current node is already in visited:
            mark isCycle = true, stop
        add current node to visited
        move to its parent

    if isCycle is true, stop checking further nodes

So the full code looks like this:

function TreeConstructor(strArr) {
  const obj = {};
  const childrenCount = {};
  let hasMoreThanOneParent = false;
  let hasMoreThanTwoChildren = false;

  for (const str of strArr) {
    const [child, parent] = str.slice(1, -1).split(',').map(Number);

    // A child key appearing twice means this node has two parents
    if (child in obj) hasMoreThanOneParent = true;
    obj[child] = parent;

    // Count how many children each parent has
    childrenCount[parent] = (childrenCount[parent] || 0) + 1;
    if (childrenCount[parent] > 2) hasMoreThanTwoChildren = true;
  }

  // Walk up from every node to check for cycles
  let isCycle = false;
  for (const start of Object.keys(obj)) {
    const visited = new Set();
    let current = Number(start);

    while (current in obj) {
      if (visited.has(current)) { isCycle = true; break; } // already visited -> cycle
      visited.add(current);
      current = obj[current];
    }
    if (isCycle) break;
  }

  return !hasMoreThanOneParent && !hasMoreThanTwoChildren && !isCycle;
}

console.log(TreeConstructor(readline()));