Home > Blockchain >  Sort recursively-defined tree by given target value
Sort recursively-defined tree by given target value

Time:02-10

we have a tree where each node in the tree is an object with a required "val" property that maps to a non-unique integer and an optional "children" property that, if present, maps to an array of child nodes.

This challenge involves writing a function prioritizeNodes(tree, targetVal) which accepts a valid nested tree object conforming to the above definition. The function should sort all "children" arrays containing one or more nodes with node.val === targetVal to the front of the array. For this input, the output for a call to prioritizeNodes(tree, 7)

INPUT

{
  "val": 1,
  "children": [
    {"val": 2},
    {
      "val": 3,
      "children": [
        {
          "val": 4,
          "children": [
            {"val": 5},
            {"val": 6},
            {"val": 7}
          ]
        }
      ]
    }
  ]
}

Expected output

{
  "val": 1,
  "children": [
    {
      "val": 3, // <-- moved up
      "children": [
        {
          "val": 4,
          "children": [
            {"val": 7}, // <-- moved up
            {"val": 5},
            {"val": 6}
          ]
        }
      ]
    },
    {"val": 2}
  ]
}

Each node in a tree with a value or child matching the target was moved to the front of its respective array.

Non-prioritized nodes should be kept in their original relative ordering with respect to one another, and prioritized nodes which were moved to the front of an array should also maintain order with respect to other priority nodes in the array. Your function may mutate the parameter tree in-place in addition to returning it if you wish.

Here's what i've got so far, and i couldn't identify why it still doesn't work, can anyone provide any solution please ?

class Node {
    val;
    children;

    constructor(data) {
        this.val = data.val || null
        if(data.children?.length > 0){
            this.children = []
            this.addChildren(data.children)
        }else if(this.children?.length <= 0){
            delete this.children
        }
    }
    addChildren(children) {
        if(children?.length > 0){
            for (let i = 0; i < children.length; i  ) {
                let newNode = new Node(children[i])
                this.children.push(newNode)
            }
        }
    }
}


function repeater(node, targetVal) {
    let parentFlag = false
    if(node.children?.length > 0){
        for (let i = 0; i < node.children.length; i  ) {
            if(repeater(node.children[i], targetVal)){
                node.children.unshift(...node.children.splice(i, 1))
                parentFlag = true
            }
        }
    }
    return node.val === targetVal || parentFlag;
}

const prioritizeNodes = (oldtree, targetVal) => {
    if(!oldtree.children){
        return oldtree;
    }
    let tree = new Node(oldtree)
    for (let i = 0; i < oldtree.children.length; i  ) {
        repeater(tree, targetVal)
    }
  console.log(tree)
    return tree;
}

CodePudding user response:

shifting priority nodes into the children array will inverse the order of the priority nodes, which is not what is asked for.

I would avoid mutation and create two new children arrays in which the children are divided: one for the priority ones, and one for the other children. Then concatenate those two. Let the recursive function return both the new children array and the flag.

The code:

function prioritizeNodes(tree, targetVal) {
    function recur({val, children}) {
        if (!children) {
            return [{ val }, val === targetVal];
        }
        let categories = [[], []], 
            isPrio;
        for (let child of children) {
            [child, isPrio] = recur(child);
            categories[1-isPrio].push(child);
        }
        return [
            { val, children: categories.flat() },
            categories[0].length > 0 || val === targetVal
        ];
    }
    return recur(tree)[0];
}

// Example input
let tree = {"val": 1,"children": [{"val": 2},{"val": 3,"children": [{"val": 4,"children": [{"val": 5},{"val": 6},{"val": 7}]}]}]}

let result = prioritizeNodes(tree, 7);
console.log(result);

  • Related