I wrote a code for All Elements in Two Binary Search Trees problem on leetcode: https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

I couldn't find anyone else trying to solve it this way. I know that this code could be improved with helper() 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 sort.Ints(curr).

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.

func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
    if root1 == nil && root2 == nil {
        return []int{}
    } else if root1 != nil && root2 != nil {
        curr := getAllElements(root1.Left, root2.Left)
        if root1.Val < 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{}
}

CodePudding user response：

This is a solution for 1305. All Elements in Two Binary Search Trees

func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
    if root1 == nil && root2 == nil {
        return nil
    }
    var list1 []int
    if root1 != nil {
        list1 = inOrder(root1, list1)
    }
    
    var list2 []int
    if root2 != nil {
        list2 = inOrder(root2, list2)
    }
    
    if len(list1) == 0 {
        return list2
    }
    if len(list2) == 0 {
        return list1
    }
    
    var list3 []int
    for i, j := 0, 0;; {
        var elem1 int
        if len(list1) > i {
            elem1 = list1[i]
        } else {
            // we add the remaining elements from list2 into list3
            // there are no elements in list1
            if len(list2) > j {
                list3 = append(list3, list2[j:]...)
                break
            }
        }
        
        var elem2 int
        if len(list2) > j {
            elem2 = list2[j]
        } else {
            // we add the remaining elements from list1 into list3 
            // there are no elements in list2
            if len(list1) > i {
                list3 = append(list3, list1[i:]...)
                break
            }
        }
        
        if elem1 < elem2 {
            list3 = append(list3, elem1)
            i  
        } else {
            list3 = append(list3, elem2)
            j  
        }
    }
    return list3
}

func inOrder(node *TreeNode, list []int) []int {
    if node.Left != nil {
        list = inOrder(node.Left, list)
    }
    list = append(list, node.Val)
    if node.Right != nil {
        return inOrder(node.Right, list)
    }
    return list
}

CodePudding user response：

Why would you need to do any sorting at all? By definition, binary trees are ordered. All you have to do is

• Walk each tree, producing a list containing that tree's contents.
• You now have two ordered lists.
• Merge them to produce a single, ordered list.

Let us assume we have a tree struct, thus:

type tree *struct {
    left    tree
    right   tree
    payload int
}

Walking such a binary tree to produce an ordered list is trivial:

func treeToSlice(root tree) []int {
    arr := make([]int, 0)
    var visit func(tree)

    visit = func(curr tree) {

        if curr.left != nil {
            visit(curr.left)
        }

        arr = append(arr, curr.payload)

        if curr.right != nil {
            visit(curr.right)
        }
    }

    visit(root)

    return arr
}

Merging two such ordered lists is likewise trivial:

func merge( a []int, b []int ) []int {
    c := make([]int, len(a) len(b)) // merged list to be returned
    i := 0                          // current element of A
    j := 0                          // current element of B
    k := 0                          // current element of C

    // while we have both A and B...
    for ; i < len(a) && j < len(b) ; k   {
        if a[i] <= b[j] {
            c[k] = a[i]
            i  
        } else {
            c[k] = b[j]
            j  
        }
    }

    // if we have any As left....
    for ; i < len(a) ; k   {
        c[k] = a[i]
        i  
    }

    // if we have any Bs left...
    for ; j < len(b) ; k   {
        c[k] = b[j]
        j  
    }

    return c
}

And with those, converting two binary trees into a single ordered list is... triviality itself:

func twoBTreesToOrderedSlice( t1 tree, t2 tree ) []int {
    return merge(
        treeToSlice( t1 ),
        treeToSlice( t2 ),
    )
}

While you could use goroutines and channels to walk the trees in parallel, but the code is no more "elegant", and due to channel overhead and the cost of synchronization, it's virtually guaranteed to be less performant than the simpler "walk each tree to build ordered lists and then merge the two ordered lists.

I suppose, though, it probably saves a little space.

type tree *struct {
  left    tree
  right   tree
  payload int
}

func walkTree( root tree, ch chan int ) {
  var visit func(tree)
  
  visit = func(node tree) {
  
    if node != nil {
      
      visit(node.left)
      
      ch <- node.payload
      
      visit(node.right)

    }
  }

  visit(root)
  close(ch)

}

func btreesToOrderedSlice( t1 tree, t2 tree ) []int {
  arr := make([]int, 0)
  
  ch1 := make(chan int)
  ch2 := make(chan int)

  go walkTree(t1, ch1)
  go walkTree(t2, ch2)
  
  x, haveX := <-ch1
  y, haveY := <-ch2
  
  for haveX && haveY {
    if x <= y {
      arr = append(arr, x)
      x, haveX = <-ch1
    } else {
      arr = append(arr, y)
      y, haveY = <-ch2
    }
  }
  
  for x = range ch1 {
    arr = append(arr, x)
  }
  
  for y = range ch2 {
    arr = append(arr, y)
  }
  
  return arr
}