title: non-binary tree search and insertion
body: <p>I searched a bit but haven't found the answer to this question..</p>
  
  <p>I built a non-binary tree, so each node can have any number of children (called n-ary tree i think)</p>
  
  <p>To help with searching, I gave every node a number when i built the tree, so that every node's child nodes will be bigger, and all the node to the right of the it will be bigger as well. </p>
  
  <p>something like this:</p>
  
  <p><a href="https://i.stack.imgur.com/F5aFS.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/F5aFS.png" alt="tree stucture"></a></p>
  
  <p>This way I get logn time for search</p>
  
  <p>The problem comes when I want to insert nodes. This model would not work if I want to insert nodes anywhere but the end. </p>
  
  <p>I thought of a few ways to do it,</p>
  
  <ol>
  <li><p>insert the new nodes at the desired location, then update the number of all the nodes "behind" it.</p></li>
  <li><p>instead of using a single number to represent each node, use an array of numbers. The numbers in the array will represent its location on that specific level. For example, node 1 will be {0}. Node 9 will be {0,2}. Node 7 will be {0, 0, 1, 2}. Now when inserting, I just need to change the numbers on that level. </p></li>
  <li><p>forget all the numbering and just compare every node until the correct one is found. Insertion don't need to care about numbers either.</p></li>
  </ol>
  
  <p>My question is, which way would be better? I'm not sure if using an array of integers to represent each node is very fast.. maybe it is still faster than the first way? Are there other ways of going about this? </p>
  
  <p>Thank you in advance.</p>