class TreeNode {
    constructor(key){
        this.key = key;
        this.sons = []
    }
    insert(key){
        let node = new TreeNode(key);
        this.sons.push(node)  
        return node
    }
}
}

let str = 'hello word'
let str2 = 'abcdefg'

// Root node
let root = new TreeNode("root")

createTree(str,root)

createTree(str2,root)

function createTree(strs,parent){
    if(strs.length !==0){
        let found = parent.sons.find((item)=>item.key === strs[0])
        if(found){
            let newStrs = strs.slice(1)
            createTree(newStrs,parent)
        }else{
            let node = parent.insert(strs[0])
            let newStrs = strs.slice(1)
            createTree(newStrs,node)
        }
      
    }else if(strs.length === 0){
        console.log('Creation complete',root)
        return root
    }
}

// Use stack to implement depth-first search
// General idea is to push all nodes into array, then take last one to process, delete while processing.
// Until none left
function dfsByStack(root) {
    let stack = []; 
      // Create stack object, js uses array instead of stack, each element is TreeNode type
    stack.push(root);    // Initialize, push root node
    while (stack.length) {  // As long as stack has nodes, continue
    // Take out just pushed node
    let node = stack.pop();  // Pop top node of stack, get first node entered
    if (node.sons.length == 0) {
      // Already reached leaf node, output
        console.log('Already reached leaf node',node.key)
    } else {
      // Non-leaf node, traverse each of its child nodes
      // Note, here uses a temporary stack stackTemp
      // This is to maintain traversal order, consistent with recursive traversal order
      // If order not required, can directly push to stack
      let stackTemp = []
      for (let index = 0; index < node.sons.length; index++) {
          const son = node.sons[index];
          console.log(son.key)
          stackTemp.push(son)
      }
      //  Put each node into stack sorted
      //  Reverse order
      while (stackTemp.length) {
        stack.push(stackTemp.pop());
      }
    }
    }
  }  

bfs(root.sons)
function bfs(queue){
    if(queue.length === 0){console.log('Finished');return;}
    let tmpQueue = []
    for (let index = 0; index < queue.length; index++) {
        const element = queue[index];
        console.log(element.key)
        if(element.sons && element.sons.length){
           // Prepare data needed for next search
            tmpQueue.push(...element.sons)
        }
    }
    bfs(tmpQueue)
}