def insert(x,nums):
    #BASE CASE - do not forget
    if nums == []:
        return [x]
    #RECURSIVE CASE
    if x <= nums[0]:
        return [x] + nums
        #nums.insert(0,x)
        #return nums
    else:
        return [nums[0]] + insert(x,nums[1:])
    

def isort(nums):
    # BASE CASE
    if nums == []:
        return []
    #RECURSIVE CASE
    return insert(nums[0],isort(nums[1:]))

insert(25,[13,16,36,92])

[13, 16, 25, 36, 92]

isort([25,16,13,36,92])

[13, 16, 25, 36, 92]

xs = [20,30,40]
xs.insert(0,10)
print(xs)

[10, 20, 30, 40]

class TreeNode:

  def __init__(self, left, symbols, weight, right):
    self._left = left
    self._symbols = symbols
    self._weight = weight
    self._right = right

  def __str__(self):
    if self._left == None and self._right == None:
      return "TreeNode(None,"+str(self._symbols)+","+str(self._weight)+",None)"
    elif self._left == None:
      return "TreeNode(None,"+str(self._symbols)+","+str(self._weight)+","+str(self._right)+")"
    elif self._right == None:
      return "TreeNode("+str(self._left)+","+str(self._symbols)+","+str(self._weight)+",None)"
    else:
      return "TreeNode("+str(self._left)+","+str(self._symbols)+","+str(self._weight)+","+str(self._right)+")"

tlist = [TreeNode(None,set('E'),1,None), TreeNode(None,set('F'),1,None),
         TreeNode(None,set('G'),1,None), TreeNode(None,set('B'),3,None),
         TreeNode(None,set('A'),8,None)]

t = TreeNode(TreeNode(None,set('C'),1,None),{'C','D'},2,TreeNode(None,set('D'),1,None))

# takes as input a new tree t and a list of sorted trees and
# returns a sorted list of trees after inserting t into tlist.
def insertHT(t,tlist):
    if tlist == []:
        return [t]
    if t._weight <= tlist[0]._weight:
        return [t] + tlist
    else:
        return [tlist[0]] + insertHT(t,tlist[1:])

result = insertHT(t,tlist)
for t in result:
    print(t)

TreeNode(None,{'E'},1,None)
TreeNode(None,{'F'},1,None)
TreeNode(None,{'G'},1,None)
TreeNode(TreeNode(None,{'C'},1,None),{'D', 'C'},2,TreeNode(None,{'D'},1,None))
TreeNode(None,{'B'},3,None)
TreeNode(None,{'A'},8,None)

repea using recursion:
    combine first two trees into one
    insertHT combinedTree into list of trees without first two trees

s = "FAD"
huffman_code(s) = "01111"+"1"+"0101"  # 0111110101

  Cell In[19], line 6
    huffman_code(s) = "01111"+"1"+0101"
                                  ^
SyntaxError: leading zeros in decimal integer literals are not permitted; use an 0o prefix for octal integers