title: Need help constructing string with parenthesis from Binary Tree
body: <p>I am trying to solve the following algorithm question:</p>
  
  <p>You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.</p>
  
  <p>The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree.</p>
  
  <p>Example 1:
  Input: Binary tree: [1,2,3,4]</p>
  
  <pre><code>       1
       /   \
      2     3
     /
    4
  </code></pre>
  
  <p>Output: "1(2(4))(3)"</p>
  
  <p>Explanation: Originallay it needs to be "1(2(4)())(3()())",
  but you need to omit all the unnecessary empty parenthesis pairs.
  And it will be "1(2(4))(3)".</p>
  
  <p>Example 2:
  Input: Binary tree: [1,2,3,null,4]</p>
  
  <pre><code>       1
       /   \
      2     3
       \
        4
  </code></pre>
  
  <p>Output: "1(2()(4))(3)"</p>
  
  <p>Explanation: Almost the same as the first example,
  except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.</p>
  
  <p>I have written the following code:</p>
  
  <pre><code>class TreeNode {
      constructor(val, left, right) {
          this.val = (val === undefined ? 0 : val)
          this.left = (left === undefined ? null : left)
          this.right = (right === undefined ? null : right)
      }
  }
  
  const tree2str = (t) =&gt; {
      const result = []
      const stack = []
  
      const dfs = (current) =&gt; {
          if (current === null) return
          result.push(current.val)
          if (!current.left &amp;&amp; current.right) result.push('(')
          if (current.left) {
              result.push('(')
              stack.push(')')
              dfs(current.left)
          }
          while (stack.length) {
              result.push(stack.pop())
          }
          if (!current.left &amp;&amp; current.right) stack.push(')')
          if (current.right) {
              result.push('(')
              stack.push(')')
              dfs(current.right)
          }
      }
      dfs(t)
      return result.join('')
  }
  </code></pre>
  
  <p>The test cases I have so far:</p>
  
  <pre><code>const tree = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3))
  const tree2 = new TreeNode(1, new TreeNode(2, null, new TreeNode(4)), new TreeNode(3))
  const tree3 = new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)))
  
  console.log(tree2str(tree)) // "1(2(4)())(3()())" ==&gt; "1(2(4))(3)"
  console.log(tree2str(tree2)) // "1(2()(4))(3)"
  console.log(tree2str(tree3)) // "1(2(3)(4))" instead got "1(2(3))(4)"
  </code></pre>
  
  <p>Only two work, however, I am having trouble with the third, and can't spot where I am going wrong.</p>