title: Building a binary tree from a recursively defined string notation
body: <p>I've been struggling with this for several hours now, so after Googling incessantly and finding little to go on, I finally decided to see what kind of help SO might offer me on a piece of my latest CS hw.</p>
  <p>Our assignment is to read in and store binary trees, which are given to us in a format like this:
  ( (root) (left_subtree) (right_subtree))</p>
  <p>Each set of matching parens represents a tree, the first thing is the root, the next is the left subtree, and then the right subtree. A subtree doesn't need to be surrounded by parens if it's a leaf, but it can be. To clarify what I mean by that, see the following examples, which are all valid representations of the tree pictured below the code block.</p>
  <pre><code>(A B C)
  (A (B) C)
  (A B (C))
  ((A) (B) (C))
  </code></pre>
  <p><a href="https://i.stack.imgur.com/GGW8x.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/GGW8x.jpg" alt="a tree" /></a><br />
  <sub>(source: <a href="http://faculty.otterbein.edu/psanderson/csc205/notes/binaryTreeABC.jpg" rel="nofollow noreferrer">otterbein.edu</a>)</sub></p>
  <p>For a more complex example that illustrates the recursive nature of the definition a bit better, one possible string for the following tree would be:</p>
  <pre><code>(F(B A (D C E)) (G () (I (H))))
  </code></pre>
  <p>Note that, in the right subtree of F [i.e. &quot;(G () (I (H)))&quot;], the &quot;()&quot; is necessary after G to denote the empty left child - but also note that the right subtree of G [&quot;(I (H))&quot;] could also have been represented more simply as &quot;(I H)&quot;.</p>
  <p><img src="https://upload.wikimedia.org/wikipedia/commons/6/67/Sorted_binary_tree.svg" alt="a bigger tree" /></p>
  <p>I have a binary tree class (and matching TreeNode class) completed except for the essential function to build the tree from this input, but I just can't seem to wrap my head around how exactly to parse the string. I have a general idea of how to do it - at least, how the recursion works - but how exactly to go about breaking down the problem into smaller parts is going over my head.</p>
  <pre><code>//pseudocode musings
  TreeNode* Tree::buildFromString(string s){
  TreeNode* temp = NULL
  if ( the string doesn't represent an empty tree )
    temp = new TreeNode
    temp-&gt;data = part of s representing root
    temp-&gt;leftChild = buildFromString( part of s representing left subtree)
    temp-&gt;rightChild = same as above, but with right subtree     
  }
  return temp;
  </code></pre>
  <p>I'm not having trouble with the recursion per se -- it makes sense, it's not that hard to trace it roughly in your head. The base case works - you kick out of the recursion and head back up the calls once you reach a leaf node, linking the subtrees as you go back.</p>
  <p>But I can't figure out how to break the problem down into smaller pieces in the code, which is obviously the whole point of recursion. I want to create substrings of the original to pass to the recursive calls, but I just can't seem to wrap my head around how to get the appropriate pieces.</p>
  <p>Got any ideas?</p>