Skip to content

Instantly share code, notes, and snippets.

@linuxandchill

linuxandchill/All Elements in Two Binary Search Trees

Last active September 5, 2020 22:37
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save linuxandchill/e8fd606387099e082a16869085831d0b to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save linuxandchill/e8fd606387099e082a16869085831d0b to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. linuxandchill renamed this gist Sep 5, 2020. 1 changed file with 0 additions and 0 deletions.
    0 All Elements BST → All Elements in Two Binary Search Trees
    View file
    File renamed without changes.
  2. linuxandchill created this gist Sep 5, 2020.
    47 changes: 47 additions & 0 deletions All Elements BST
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,47 @@
    class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
    one = self.traverse(root1)
    two = self.traverse(root2)

    temp = one + (len(two) * [0])

    self.merge(temp, len(one), two, len(two))

    return temp

    # [1,2,4,0,0,0]
    # [0,1,3]
    def merge(self, nums1, m, nums2, n):
    k = len(nums1) - 1
    m = m - 1
    n = n - 1

    while m >= 0 and n >= 0:
    if nums1[m] > nums2[n]:
    nums1[k] = nums1[m]
    k -= 1
    m -= 1
    else:
    nums1[k] = nums2[n]
    k -= 1
    n -= 1

    while n >= 0:
    nums1[k] = nums2[n]
    k -= 1
    n -= 1

    return nums1

    def traverse(self, root):
    output = []

    def helper(node):
    if not node:
    return
    helper(node.left)
    output.append(node.val)
    helper(node.right)

    helper(root)
    return output