My check for whether a graph is a Binary Tree always returns false

I have this question that is medium level and couldn’t even think on how to solve this problem, my solution could be overkill as I have no idea on how to traverse a bunch of numbers in an array to check whether it is a binary tree or not. The program always returns false no matter what

If you have a better answer to the question that would be perfect

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 a 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)"]

    4 
   /
  2
 / 
1   7

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 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

Examples

input: ["(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"]
output: true


input ["(1,2)", "(1,3)"]
output: false

I came out with an attempt, but it always returns false. Most likely my code is overkill.

class Node {
  // The constructor
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
  // Basic insert node
  insert(value) {
    let currentNode = this;
    while (true) {
      if (value < currentNode.value) {
        if (currentNode.left === null) {
          currentNode.left = new Node(value);
          break;
        } else {
          currentNode = currentNode.left;
        }
      } else {
        if (currentNode.right === null) {
          currentNode.right = new Node(value);
          break;
        } else {
          currentNode = currentNode.right;
        }
      }
    }
    return currentNode
  }
    // check if BST is valid or not
    isValidBST(node, min = null, max = null) {
    if (!node) return true;
    if (max !== null && node.value >= max) {
      return false;
    }
    if (min !== null && node.value <= min) {
      return false;
    }
    const leftSide = this.isValidBST(node.left, min, node.value);
    const rightSide = this.isValidBST(node.right, node.value, max);
    return leftSide && rightSide;
  }
}

// Convert the strings to a number 
function convertListToNumber(str, i) {
  return str[i].split('(').join('').split(')').join('').split(',').join('')
}

This is the main function

function TreeConstructorTwo(strArr) { 
  // code goes here  
  startValueFromList = convertListToNumber(strArr, 0)
  // Parent Node here
  startParentNode = startValueFromList[1];
  // Child Node here
  startChildNode = startValueFromList[0];
  // Add parent Node and childNode
  node = new Node(startParentNode);
  node.insert(startChildNode);
  // Loop through the entire array
  for (i = 1; i < strArr.length; i++) {
    myListValue = convertListToNumber(strArr, i);
    console.log(myListValue.length)
    // Loop the "12" in the string and convert it to a number
    for (j = 0; j < myListValue.length; j++) {
       node.insert(myListValue[j])
    }
    parentNode = Number(myListValue[0])
  }
  // Check if the BST is valid or not
  return node.isValidBST(node)
}

// keep this function call here 
console.log(TreeConstructorTwo(["(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"]));

Answer

You seem to have misunderstood the assignment. The function should return true when the represented tree is a binary tree, not necessarily a binary search tree.

Your code is creating a tree from the first element and then takes any next node to insert it into that tree keeping with the binary search property, without taking into account that the pair from the input demands that the first is a direct child of the second. (Your variable parentNode is not used for anything)

Instead, you should just look at the child-parent relationships that are given in the input as representing edges, and use that information to build the graph. Finally you should verify that that graph represents a binary tree. Think about what are the distinctive characteristics of a binary tree and how to verify them.

Hint 1:

No node should have two parents

Hint 2:

No node should have 3 children

Hint 3:

All upward paths should end in the same node (the root)

The spoiler solution below does not return true/false, but a string that indicates whether the tree is “ok”, or why it is not. This is more useful for debugging and still easy to convert to a boolean.

// This function returns the reason why it considers the input
// not a binary tree. "ok" otherwise.
function isBinaryTree(edgesStr) {
    const childToParent = new Map(edgesStr.map(edge => edge.match(/d+/g)));
    // No node should have 2 parents
    if (childToParent.size < edgesStr.length) return "node with two parents";
    // No node should have 3 children
    const degree = {};
    for (const [child, parent] of childToParent) {
         if ((++degree[parent] || (degree[parent] = 1)) > 2) return "node with three children";
    }
    // All upward paths lead to the same root (no cycles)
    const nodes = {};
    let current = 0;
    let countRoots = 0;
    for (let node of childToParent.keys()) {
        current++;
        while (node && !nodes[node]) {
            nodes[node] = current;
            node = childToParent.get(node);
        }
        if (!node && countRoots++) return "disconnected";
        if (node && nodes[node] == current) return "cycle";
    }
    return "ok";
}

const tests = [
    ["(2,1)", "(3,1)", "(4,2)", "(5,2)", "(6,3)", "(7,3)"],
    ["(1,2)", "(3,2)", "(2,12)", "(5,2)"],
    ["(2,1)", "(3,1)", "(5,4)", "(5,2)"],
    ["(2,1)", "(4,3)"],
    ["(1,2)", "(3,4)", "(4,5)", "(5,3)"],
];

for (const test of tests) {
    console.log(isBinaryTree(test));
}

NB: I would name the function with an initial lowercase letter as it is the common practice to reserve initial capital letters for class names.