Return to Question

I am solving this problem using an N-ary tree form, explained visually in this picture:

Using Example 2 ie:

Input: nums = [3,30,34,5,9]
Output: "9534330"

enter image description here

I have written some code so far (wip) that aims to traverse and print this tree:

public class LargestNumber {
 static class Node {
 int key;

 ArrayList<Node> child;
 Node(int val) {
 key = val;
 child = new ArrayList<>();
 }
 }
 // PS: this function re-used from https://www.geeksforgeeks.org/preorder-traversal-of-a-n-ary-tree/
 static void preorderTraversal(Node root) {
 Stack<Node> stack = new Stack<>();
 // 'Preorder'-> contains all the
  // visited nodes
  ArrayList<Integer> Preorder = new ArrayList<>();
 stack.push(root);
 while (!stack.isEmpty()) {
 Node temp = stack.peek();
  stack.pop();
 // store the key in preorder vector(visited
 // list)
  Preorder.add(temp.key);
 // Push all of the child nodes of temp into
 // the stack from right to left.
 for (int i = temp.child.size() - 1; i >= 0; i--) {
 stack.push(temp.child.get(i));
 }
 }
 for (Integer i : Preorder) {
 System.out.print(i + " ");
 }
  System.out.println();
 }
 public static void main(String[] args) {
 // input nodes
 /*
 *
 / | \
 / | \
 3 5 9
 / \
 / \
 0 4
 * */
 //PS: First tryout: manually add node before deciding which tree/algorithm traversal to use. Then build functions that will add nodes.
 Node root = new Node(-1);//val =-1 ie no val ie main node
 root.child.add(new Node(9)); // child 0
 root.child.add(new Node(5)); // child 1
 root.child.add(new Node(3)); // child 2

 // Node with key : 3
 Node nodeThreeParen = root.child.get(2);

 nodeThreeParen.child.add(new Node(4));
 nodeThreeParen.child.add(new Node(0));

 preorderTraversal(root);
 }
}
// This as is will print: -1 9 5 3 4 0 

• Am I correct to consider this an n-ary tree, or is it a trie? or?
• Which traversal algorithm is adequate to use with such trees knowing that I want to traverse from leafs to parents following:

Notes:

• This is not the final code; it is a work in progress and will be modified/refactored once I know what type of trees/traversal to use. For example, to turn "34" to two nodes "3" and "4" will use modulus and division to strip the values as needed, etc.
• The root node (which key is -1) will not show up in the final output
• Once I know which tree to use and which traversal algorithm, the final string will be the traversal of the tree --> to string.

Here is my solution:

class Solution {
 // custom comparator: comparing integers as strings
 // to decide which to place before the other.
 static class SortByFirstDigit implements Comparator<Integer> {
 @Override
 public int compare(Integer i1, Integer i2) {
 String a = Integer.toString(i1);
 String b = Integer.toString(i2);
 //compare integers as strings to know which will be picked up ie 'ab' and 'ba' for example
 return Integer.compare(0, (a + b).compareTo(b + a));
 }
 }
 // REF: Convert int[] to Integer[]
 // function toConvertInteger is taken from stackoverflow at:
 // https://stackoverflow.com/a/31967630/1063062
 public static Integer[] toConvertInteger(int[] ids) {
 Integer[] newArray = new Integer[ids.length];
 for (int i = 0; i < ids.length; i++) {
 newArray[i] = Integer.valueOf(ids[i]);
 }
 return newArray;
 }
 public String largestNumber(int[] nums) {
 Integer[] Nums = toConvertInteger(nums);
 Arrays.sort(Nums, new SortByFirstDigit());
 StringBuilder builder = new StringBuilder();
 for (int s : Nums) builder.append(s);
 
 //if we get a string of all zeros, strip to 1 zero.
 if (builder.toString().matches("^[0]+$")) return "0";
 
 return builder.toString();
 }
}

• This code passes all test but runs in around 9ms. What part(s) of the code are making it slow? and how to make it faster?
• Or, is it better to solve this problem in other ways (ie more performant) like for example using a N-ary tree for example? While analyzing the problem I had at some point thought of a tree algorithm which I will explain graphically in this picture:enter image description here

It will traverse from leafs to parents following:

I have written some code so far (wip) that aim to traverse and print this tree:

PS:

• This is not the final code, it is a work in progress and will be modified/refactored once I know what type of trees/traversal to use. For example to turn "34" to two nodes "3" and "4" will use modulus and division to strip the values as needed etc...
• The root node (which key is -1) will not show up in the final output
• Once I know which tree to use and which traversal algorithm, the final string will be the traversal of the tree --> to string.

I have written some code so far (wip) that aims to traverse and print this tree:

Notes:

• This is not the final code; it is a work in progress and will be modified/refactored once I know what type of trees/traversal to use. For example, to turn "34" to two nodes "3" and "4" will use modulus and division to strip the values as needed, etc.
• The root node (which key is -1) will not show up in the final output
• Once I know which tree to use and which traversal algorithm, the final string will be the traversal of the tree --> to string.