title: Algorithm for Parsing an XML
body: <p>I was reading one of the interview <a href="http://www.glassdoor.com/Interview/One-of-the-interviewers-asked-me-to-write-two-algorithms-for-parsing-xml-one-that-was-as-memory-efficient-as-possible-the-QTN_22756.htm" rel="nofollow noreferrer">question</a> about parsing an XML.</p>
  
  <p>I wrote a very high level and incomplete skeleton of the algorithm , and was looking for some help in writing a simple algo [I assume one exists, because this was asked as an interview question so should be doable in 45 mins I guess]. </p>
  
  <p>Here is my attempt:</p>
  
  <pre><code>   // Assume well-formedness
      public static Node parseXML(String xml)
      {
  
          Node root = new XMLParse().new Node();
  
          while(!helper.endOfElements())
          {
              // Returns name of root element
              root.name = helper.getName(xml);
              // Returns value of root element
              root.name = helper.getValue(xml);
  
              // returns each child in a String and returns all such children as 
              // a String Array
              // Basically splits based on &lt;&gt; &lt;/&gt; elements and return that as a String
              String[] children = helper.getChildren(xml);
  
              if(children.length!=0)
              {
                  root.childList = new ArrayList&lt;XMLParse.Node&gt;();
                  for(int i=0; i&lt;children.length;i++)
                  {
                      root.childList.add(parseXML(children[i]));
                  }
              }
  
          }
  
  
          return root;
      }
  
  
      class Node
      {
          String name;
          String value;
          List&lt;Node&gt; childList;
  
          public String getName()
          {
              return name;
          }
  
          public String getValue()
          {
              return value;
          }
  
          public List&lt;Node&gt; getChildList()
          {
              return childList;
          }
  
      }
  
  
  Class helper()
  {
  
  // Returns the name of the root of the xml
  public static String getName(String XML);
  
  // Returns the value of the root of the xml
  public static String getValue(String XML)
  
  // Splits the XML into top level childern of the root of the passed XML
  public static String[] getChildren(String XML)
  
  }
  </code></pre>
  
  <p>I am hoping someone can give me a pseudo-code/code for doing this or may be provide an easy way of implementing the helper function in my algo. </p>
  
  <p>I know there are built in classes to do this like in <a href="http://www.developerfusion.com/code/2064/a-simple-way-to-read-an-xml-file-in-java/" rel="nofollow noreferrer">here</a> , but using them would beat the purpose I guess. Also, many things used in this link are just interfaces so I couldnt find any implementation of say  <code>docBuilder.parse (new File("book.xml"))</code> method. </p>