Tree Generation Algorithm

I want to generate a tree with the below structure, it will take an input 'n' to generate the tree. Is there any algorithm I can use. 0 0

Solution 1:

You can use recursion. Here is a runnable snippet in JavaScript, which defines a Node class and a static method that will create the tree. When you enter a value for n, the corresponding tree will be displayed in JSON format:

classNode {
    constructor(value, children=[]) {
        this.value = value;
        this.children = children;
    }
    staticcreateTree(n, level=1, value=0) {
        returnnewNode(value, Array.from({length: (level+1) % (n+1)}, (_, i) =>this.createTree(n, level+1, i)
        ));
    }
}

// I/O handlinglet input = document.querySelector("input");
let output = document.querySelector("pre");

input.addEventListener("input", refresh);
refresh();

functionrefresh() {
    let n = +input.value;
    if (n >= 1 && n <= 8) {
        let tree = Node.createTree(n);
        output.textContent = JSON.stringify(tree, null, 4);
    } else {
        output.textContent = "Please enter a value between 1 and 8";
    }
}

n: <inputtype="number"value="3"min="1"max="8"size="4"><br><pre></pre>

The snippet does not accept values above 8 as the size of the tree grows exponentially.

Solution 2:

Another recursive approach:

functionto_tree(n, w = 1){
   var d = {}
   for (var i = 0; i < w; i++){
      d[i] = n > 0 ? to_tree(n-1, w+1) : null;
   }
   return d
}
console.log(to_tree(3))

Solution 3:

The branches are independent to each other so you can do it fairly easy with a recursive function containing the parameters current_depth and n

Sample Code

def tree(current_depth, n):
   if current_depth == n:
     return {i:i for i in range(n)}
   return {i:tree(current_depth + 1, n) for i in range(current_depth + 1)}


print(tree(1,1))
print(tree(1,2))
print(tree(1,3))

# Output
# {0: 0}
# {0: {0: 0, 1: 1}, 1: {0: 0, 1: 1}}
# {0: {0: {0: 0, 1: 1, 2: 2}, 1: {0: 0, 1: 1, 2: 2}, 2: {0: 0, 1: 1, 2: 2}}, 1: {0: {0: 0, 1: 1, 2: 2}, 1: {0: 0, 1: 1, 2: 2}, 2: {0: 0, 1: 1, 2: 2}}}