title: How to find the absolute path of a node (file or directory) in this file system model
body: <p>This was actually a question asked to me during a recent interview and I was clean bowled. </p>
  
  <p>The question was to design a database to represent a file system where -  </p>
  
  <ul>
  <li>there is a root directory and many files/directories are present inside it.</li>
  <li>there can be any number of directories/files inside a directory.</li>
  </ul>
  
  <p><strong>Requirements</strong>   </p>
  
  <ul>
  <li>find all the files present in the same directory of a given a file.</li>
  <li>given a file/directory, find its path from the root.</li>
  </ul>
  
  <p><strong>Condition</strong> 
     - There has to be one database table for the model. Not mandatory, but good to have as the Interview question had this condition.</p>
  
  <p>I did not know that making a tree and numbering it as shown in the following diagram makes it so much more optimized - </p>
  
  <p><img src="https://i.stack.imgur.com/bTOMK.png" alt="enter image description here"></p>
  
  <p>The useful property of the above tree structure is that - </p>
  
  <ul>
  <li>Considering any two subtrees, e.g. Subtree A (dir2 and its children) and Subtree B (dir3 and its children), the numbers of all the nodes in Subtree A will be lesser than the Next_Subtree_First_Node, which is dir3 in this case. </li>
  </ul>
  
  <p>Then if we store the info in a database structure like this - </p>
  
  <pre><code>_______________________________________________________________________
  Sequence_Number    Name                 type   
  -----------------------------------------------------------------------
  0                  Parent Directory     Dir  
  1                  dir1                 Dir  
  2                  file1                File  
  3                  file2                File  
  4                  file3                File  
  5                  dir2                 Dir  
  ...
  
  ________________________________________________________________________
  </code></pre>
  
  <p><strong>NOTE</strong> - The above structure is what I remember during the discussion. This may not be the best structure to solve the problem. Please let me know if some change is needed. </p>
  
  <p>The first query will be like this - </p>
  
  <p><strong>Find all files in the same directory</strong>  </p>
  
  <pre><code>Select Name From File_System 
    where Sequence_Number Between Next_Subtree_First_Node 
      and Previous_Subtree_Last_Node 
      and type = "File";
  </code></pre>
  
  <p><strong>My Questions</strong>  </p>
  
  <ul>
  <li>The above query will return all the required files, but how do I know the Next_Subtree_First_Node and Previous_Subtree_Last_Node beforehand. </li>
  </ul>
  
  <p>E.g. for file4, </p>
  
  <p>Next_Subtree_First_Node = 7 and 
  Previous_Subtree_Last_Node = 4.</p>
  
  <ul>
  <li>I am not sure what should be the logic of the absolute path finding query. Please give some ideas. </li>
  </ul>
  
  <p>E.g. given file7, the result should be - </p>
  
  <p>Parent Directory / dir3 / dir4 / file7.</p>