title: All Elements in Two Binary Search Trees
body: <p>I wrote a code for All Elements in Two Binary Search Trees problem on leetcode:
  <a href="https://leetcode.com/problems/all-elements-in-two-binary-search-trees/" rel="nofollow noreferrer">https://leetcode.com/problems/all-elements-in-two-binary-search-trees/</a></p>
  <p>I couldn't find anyone else trying to solve it this way. I know that this code could be improved with <code>helper()</code> function, but the main problem is sorting, is there some elegant way to avoid it while walking both trees at the same time? See line with <code>sort.Ints(curr)</code>.</p>
  <p>What I'm looking for is a way to walk 2 trees at the same time and fill the answer array directly in sorted order, without additional arrays.</p>
  <pre class="lang-golang prettyprint-override"><code>func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
      if root1 == nil &amp;&amp; root2 == nil {
          return []int{}
      } else if root1 != nil &amp;&amp; root2 != nil {
          curr := getAllElements(root1.Left, root2.Left)
          if root1.Val &lt; root2.Val {
              curr = append(curr, root1.Val)
              curr = append(curr, root2.Val)
          } else {
              curr = append(curr, root2.Val)
              curr = append(curr, root1.Val)
          }
          curr = append(curr, getAllElements(root1.Right, root2.Right)...)
          sort.Ints(curr) //no TLE, but how to walk both trees at the same time, like in this code, to avoid this sorting?
          return curr
      } else if root1 != nil {
          curr := getAllElements(root1.Left, nil)
          curr = append(curr, root1.Val)
          curr = append(curr, getAllElements(root1.Right, nil)...)
          return curr
      } else if root2 != nil {
          curr := getAllElements(nil, root2.Left)
          curr = append(curr, root2.Val)
          curr = append(curr, getAllElements(nil, root2.Right)...)
          return curr
      }
      return []int{}
  }
  </code></pre>