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

Question

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 1

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.

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.

Answer 2

Recently I've did the solution for this task, check my solution below:

const isBinaryTree = (array) => {
  const getChildrenNode = (node) => node.slice(1, 2);
  const childrenNodes = array.map(x => getChildrenNode(x));
  const isChildrenNodesIsUnique = (array) => array.length === new Set(array).size;
  
  return isChildrenNodesIsUnique(childrenNodes);
};


console.log(isBinaryTree(["(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"]));
console.log(isBinaryTree(["(1,2)", "(1,3)"]));

Answer 3

function isBinaryTree(tree) {

    isBinary = 0; 
  
    childs = tree.map(node => {
        return node.substr(1, 1)
    });
  
    parents = tree.map(node => {
        return node.substr(3, 1)
    });
    
    parents.map(parent => {
        if (!childs.includes(parent))
            isBinary++;
    });
  
    isBinary = isBinary == 1 ? true : false;
  
    return isBinary;

}

Answer 4

I did this by collecting the parent ids in an array and checking if any parent id is exists more than twice. Not sure though it will

["(1,2)", "(3,2)", "(2,12)", "(5,2)"]

since 2 came 3 times at the right of the pair its a false (a root or leaf node cannot have more than 2 childs)

Answer 5

const isBinaryTree = (array) => {

  // find the parent child
  const parentChildFreq = (value) => {

    const charFreqency = {};
    for (let index = 0; index < value.length; index++) {
      if (charFreqency[value[index]]) {
        // if parent have more the 2 children then this is not binary-tree
        if (charFreqency[value[index]] >= 2) {
          return false;
        }
        charFreqency[value[index]] += 1;
      } else charFreqency[value[index]] = 1;
    }
    return true;
  };

  const isChildrenNodesIsUnique = (array) =>
    array.length === new Set(array).size;

  const childrenNodes = array.map((node) => node[1]);

  let parentsNodes = array.map((node) => node[3]);
  parentsNodes = Array.from(parentsNodes, Number);
  

  return isChildrenNodesIsUnique(childrenNodes) && parentChildFreq(parentsNodes)
    ? " \n Binary-tree"
    : "not-binary-tree";
};

console.log(isBinaryTree(["(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"]));
//console.log(isBinaryTree(["(1,2)", "(3,2)", "(2,12)", "(5,2)"]));

Answer 6

I had it at a coding interview, could not make it on time but later I did this. It seems to be working but it is as good as my tests are. It seems that this two conditions are enough: -A node can have less than 3 child. -Every node has a parent but one.

  function ArrayChallenge(strArr) {
  //Make a num array
  const numArray = strArr.map((str) => {
    var mySubString = str.substring(str.indexOf("(") + 1, str.lastIndexOf(")"));
    return mySubString.split(",").map(Number);
  });

  //Get parent nodes
  const parents = numArray.map((arr) => {
    return arr[1];
  });

  //Get children nodes
  const children = numArray.map((arr) => {
    return arr[0];
  });

  //Conditions

  //a parent can't have 3 children
  const threeChildrenCondition = findRepeated(parents) < 3 ? true : false;
  const allHaveParentsButOneCondition = allHaveParentsButOne();

  //every node has a parent except for one
  function allHaveParentsButOne() {
    var parentOfAll = parents.filter(function (num) {
      return children.indexOf(num) == -1;
    });

    //Will remove duplicate numbers (parent appearing two times)
    let unique = [...new Set(parentOfAll)];

    const result = unique.length == 1 ? true : false;

    return result;
  }

  //Returns how many times a number is repeated in an array
  function findRepeated(array) {
    let repeatedNumbers = [];
    for (let i = 0; i < array.length; i++) {
      for (let j = i + 1; j < array.length; j++) {
        if (array[i] === array[j]) {
          repeatedNumbers.push(array[i]);
        }
      }
    }
    const length = repeatedNumbers.length;
    return length;
  }

  const result = threeChildrenCondition && allHaveParentsButOneCondition;

  return result;
}

//CHALLENGES

//Must be false
const f0 = ["(1,2)", "(3,2)", "(2,12)", "(5,2)"];
const f1 = ["(1,4)", "(3,2)", "(2,12)", "(5,2)"];
const f2 = ["(1,7)", "(3,7)", "(2,7)"];
const f3 = ["(10,20)", "(20,50)", "(20,8)", "(8,4)"];

console.log(ArrayChallenge(f0));
console.log(ArrayChallenge(f1));
console.log(ArrayChallenge(f2));
console.log(ArrayChallenge(f3));

//Must be true
const t0 = ["(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"];
const t1 = ["(2,3)", "(1,2)", "(4,9)", "(9,3)", "(12,9)", "(6,4)"];
const t2 = ["(1,2)", "(2,4)", "(7,4)"];
const t3 = ["(5,6)", "(6,3)", "(2,3)", "(12,5)"];
const t4 = ["(10,20)", "(20,50)"];

console.log(ArrayChallenge(t0));
console.log(ArrayChallenge(t1));
console.log(ArrayChallenge(t2));
console.log(ArrayChallenge(t3));
console.log(ArrayChallenge(t4));