#!/usr/bin/env python3

# Binary Tree Python code for M269
# Written by Phil Molyneux
# Versions (see end) 

from collections import namedtuple

EmptyBT = namedtuple('EmptyBT',[])                    #e\label{python:EmptyBT}\index{EmptyBT@\STvarKB{EmptyBT}|STmainEntry}

NodeBT = namedtuple('NodeBT'                          #e\label{python:NodeBT}\index{NodeBT@\STvarKB{NodeBT}|STmainEntry}
                   ,['dataBT','leftBT','rightBT']) 

# Tree type

from typing import TypeVar,Union,NewType

T = TypeVar('T')
Tree = NewType('Tree',Union[EmptyBT,NodeBT])

# Binary Tree Operations

def mkEmptyBT() -> Tree :                                #e\label{python:makeEmptyBT}\index{makeEmptyBT@\STvar{makeEmptyBT}|STmainEntry}
  return EmptyBT()

def mkNodeBT(x : T,t1 : Tree,t2 : Tree) -> Tree :            #e\label{python:makeBT}\index{makeBT@\STvar{makeBT}|STmainEntry}
  return NodeBT(x,t1,t2)

def isEmptyBT(t : Tree) -> bool:                           #e\label{python:isEmptyBT}\index{isEmptyBT@\STvar{isEmptyBT}|STmainEntry} 
  return t == EmptyBT()

def getDataBT(t : Tree) -> T:                              #e\label{python:getDataBT}\index{getDataBT@\STvar{getDataBT}|STmainEntry}
  if isEmptyBT(t):
    raise RuntimeError("getDataBT applied to EmptyBT()") 
  else:
    return t.dataBT   

def getLeftBT(t : Tree) -> Tree :                          #e\label{python:getLeftBT}\index{getLeftBT@\STvar{getLeftBT}|STmainEntry}
  if isEmptyBT(t):
    raise RuntimeError("getLeftBT applied to EmptyBT()") 
  else:
    return t.leftBT   

def getRightBT(t : Tree) -> Tree :                         #e\label{python:getRightBT}\index{getRightBT@\STvar{getRightBT}|STmainEntry}
  if isEmptyBT(t):
    raise RuntimeError("getRightBT applied to EmptyBT()") 
  else:
    return t.rightBT   

def heightBT(t : Tree) -> int :                            #e\label{python:heightBT}\index{heightBT@\STvar{heightBT}|STmainEntry}
  if isEmptyBT(t):
    return 0
  else:
    return (1 + max(heightBT(getLeftBT(t))
                   ,heightBT(getRightBT(t))))

def sizeBT(t : Tree) -> int :                              #e\label{python:sizeBT}\index{sizeBT@\STvar{sizeBT}|STmainEntry}
  if isEmptyBT(t) :
    return 0
  else :
    return (1 + sizeBT(getLeftBT(t))
              + sizeBT(getRightBT(t)))
              
# Example Binary Trees

# Example tree with strings

# egBSTree

egBSTree = mkNodeBT('H',                                #e\label{python:egBSTree}\index{egBSTree@\STvar{egBSTree}|STmainEntry}
             mkNodeBT('D',
               mkNodeBT('B',
                 mkNodeBT('A',mkEmptyBT(),mkEmptyBT()),
                 mkNodeBT('C',mkEmptyBT(),mkEmptyBT())
               ),
               mkNodeBT('F',
                 mkNodeBT('E',mkEmptyBT(),mkEmptyBT()),
                 mkNodeBT('G',mkEmptyBT(),mkEmptyBT())
               )
             ),
             mkNodeBT('L',
               mkNodeBT('J',
                 mkNodeBT('I',mkEmptyBT(),mkEmptyBT()),
                 mkNodeBT('K',mkEmptyBT(),mkEmptyBT())
               ),
               mkNodeBT('N',
                 mkNodeBT('M',mkEmptyBT(),mkEmptyBT()),
                 mkNodeBT('O',mkEmptyBT(),mkEmptyBT())
               )
             )   
           )  

# Example Tree with digits not strings

# egBSTreeN

egBSTreeN = mkNodeBT(7,                                #e\label{python:egBSTreeN}\index{egBSTreeN@\STvar{egBSTreeN}|STmainEntry}
              mkNodeBT(3,
                mkNodeBT(1,
                  mkNodeBT(0,mkEmptyBT(),mkEmptyBT()),
                  mkNodeBT(2,mkEmptyBT(),mkEmptyBT())
                ),
                mkNodeBT(5,
                  mkNodeBT(4,mkEmptyBT(),mkEmptyBT()),
                  mkNodeBT(6,mkEmptyBT(),mkEmptyBT())
                )
              ),
              mkNodeBT(11,
                mkNodeBT(9,
                  mkNodeBT(8,mkEmptyBT(),mkEmptyBT()),
                  mkNodeBT(10,mkEmptyBT(),mkEmptyBT())
                ),
                mkNodeBT(13,
                  mkNodeBT(12,mkEmptyBT(),mkEmptyBT()),
                  mkNodeBT(14,mkEmptyBT(),mkEmptyBT())
                )
              )   
           )             

# egBSTreeL

egBSTreeL = mkNodeBT('D',                               #e\label{python:egBSTreeL}\index{egBSTreeL@\STvar{egBSTreeL}|STmainEntry}
              mkNodeBT('B',
                mkNodeBT('A',mkEmptyBT(),mkEmptyBT()),
                mkNodeBT('C',mkEmptyBT(),mkEmptyBT())
              ),
              mkNodeBT('F',
                mkNodeBT('E',mkEmptyBT(),mkEmptyBT()),
                mkNodeBT('G',mkEmptyBT(),mkEmptyBT())
              ))

# egBSTreeNL

egBSTreeNL = mkNodeBT(3,                               #e\label{python:egBSTreeNL}\index{egBSTreeNL@\STvar{egBSTreeNL}|STmainEntry}
               mkNodeBT(1,
                 mkNodeBT(0,mkEmptyBT(),mkEmptyBT()),
                 mkNodeBT(2,mkEmptyBT(),mkEmptyBT())
               ),
               mkNodeBT(5,
                 mkNodeBT(4,mkEmptyBT(),mkEmptyBT()),
                 mkNodeBT(6,mkEmptyBT(),mkEmptyBT())
               ))

# egBSTreeLL

egBSTreeLL = mkNodeBT('B',                              #e\label{python:egBSTreeLL}\index{egBSTreeLL@\STvar{egBSTreeLL}|STmainEntry}
               mkNodeBT('A',mkEmptyBT(),mkEmptyBT()),
               mkNodeBT('C',mkEmptyBT(),mkEmptyBT())
             )

# egBSTreeNLL

egBSTreeNLL = mkNodeBT(1,                              #e\label{python:egBSTreeNLL}\index{egBSTreeNLL@\STvar{egBSTreeNLL}|STmainEntry}
                mkNodeBT(0,mkEmptyBT(),mkEmptyBT()),
                mkNodeBT(2,mkEmptyBT(),mkEmptyBT())
              )

# egBSTreeLR

egBSTreeLR = mkNodeBT('F',                              #e\label{python:egBSTreeLR}\index{egBSTreeLR@\STvar{egBSTreeLR}|STmainEntry}
               mkNodeBT('E',mkEmptyBT(),mkEmptyBT()),
               mkNodeBT('G',mkEmptyBT(),mkEmptyBT())
             )

# egBSTreeR

egBSTreeR = mkNodeBT('L',                               #e\label{python:egBSTreeR}\index{egBSTreeR@\STvar{egBSTreeR}|STmainEntry}
              mkNodeBT('J',
                mkNodeBT('I',mkEmptyBT(),mkEmptyBT()),
                mkNodeBT('K',mkEmptyBT(),mkEmptyBT())
              ),
              mkNodeBT('N',
                mkNodeBT('M',mkEmptyBT(),mkEmptyBT()),
                mkNodeBT('O',mkEmptyBT(),mkEmptyBT())
              )
            )   

# egBSTreeRL

egBSTreeRL = mkNodeBT('J',                              #e\label{python:egBSTreeRL}\index{egBSTreeRL@\STvar{egBSTreeRL}|STmainEntry}
               mkNodeBT('I',mkEmptyBT(),mkEmptyBT()),
               mkNodeBT('K',mkEmptyBT(),mkEmptyBT())
             )

# egBSTreeRR

egBSTreeRR = mkNodeBT('N',                              #e\label{python:egBSTreeRR}\index{egBSTreeRR@\STvar{egBSTreeRR}|STmainEntry}
               mkNodeBT('M',mkEmptyBT(),mkEmptyBT()),
               mkNodeBT('O',mkEmptyBT(),mkEmptyBT())
             )
            

# egBSTree1

egBSTree1 = mkNodeBT('H',                                #e\label{python:egBSTree1}\index{egBSTree1@\STvar{egBSTree1}|STmainEntry}
               mkNodeBT('D',mkEmptyBT(),mkEmptyBT()),
               mkNodeBT('L',
                 mkNodeBT('J',mkEmptyBT(),mkEmptyBT()),
                 mkNodeBT('N',
                   mkNodeBT('M',mkEmptyBT(),mkEmptyBT()),
                   mkNodeBT('O',mkEmptyBT(),mkEmptyBT())
                 )
               )   
             )  
           
# egBSTreeN1

egBSTreeN1 = mkNodeBT(7,                                #e\label{python:egBSTreeN1}\index{egBSTreeN1@\STvar{egBSTreeN1}|STmainEntry}
               mkNodeBT(3,mkEmptyBT(),mkEmptyBT()),
               mkNodeBT(11,
                 mkNodeBT(9,mkEmptyBT(),mkEmptyBT()),
                 mkNodeBT(13,
                   mkNodeBT(12,mkEmptyBT(),mkEmptyBT()),
                   mkNodeBT(14,mkEmptyBT(),mkEmptyBT())
                 )
               )   
             )  
           
# egBSTree2

egBSTree2 = mkNodeBT('H',                                #e\label{python:egBSTree2}\index{egBSTree2@\STvar{egBSTree2}|STmainEntry}
               mkNodeBT('D',
                 mkNodeBT('B',
                   mkNodeBT('A',mkEmptyBT(),mkEmptyBT()),
                   mkNodeBT('C',mkEmptyBT(),mkEmptyBT())
                 ),
                 mkNodeBT('F',
                   mkNodeBT('E',mkEmptyBT(),mkEmptyBT()),
                   mkNodeBT('G',mkEmptyBT(),mkEmptyBT())
                 )
               ),
               mkNodeBT('L',
                 mkNodeBT('J',
                   mkNodeBT('I',mkEmptyBT(),mkEmptyBT()),
                   mkEmptyBT()
                 ),
                 mkNodeBT('N',mkEmptyBT(),mkEmptyBT())
               )   
             )  
           
# egBSTreeN2

egBSTreeN2 = mkNodeBT(7,                                #e\label{python:egBSTreeN2}\index{egBSTreeN2@\STvar{egBSTreeN2}|STmainEntry}
               mkNodeBT(3,
                 mkNodeBT(1,
                   mkNodeBT(0,mkEmptyBT(),mkEmptyBT()),
                   mkNodeBT(2,mkEmptyBT(),mkEmptyBT())
                 ),
                 mkNodeBT(5,
                   mkNodeBT(4,mkEmptyBT(),mkEmptyBT()),
                   mkNodeBT(6,mkEmptyBT(),mkEmptyBT())
                 )
               ),
               mkNodeBT(11,
                 mkNodeBT(9,
                   mkNodeBT(8,mkEmptyBT(),mkEmptyBT()),
                   mkEmptyBT()
                 ),
                 mkNodeBT(13,mkEmptyBT(),mkEmptyBT())
               )   
             )  
           
# egBSTree3

egBSTree3 = mkNodeBT('H',                                #e\label{python:egBSTree3}\index{egBSTree3@\STvar{egBSTree3}|STmainEntry}
               mkNodeBT('D',
                 mkNodeBT('B',
                   mkNodeBT('A',mkEmptyBT(),mkEmptyBT()),
                   mkNodeBT('C',mkEmptyBT(),mkEmptyBT())
                 ),
                 mkNodeBT('F',
                   mkEmptyBT(),
                   mkNodeBT('G',mkEmptyBT(),mkEmptyBT())
                 )
               ),
               mkNodeBT('L',
                 mkEmptyBT(),
                 mkNodeBT('N',
                   mkNodeBT('M',mkEmptyBT(),mkEmptyBT()),
                   mkNodeBT('O',mkEmptyBT(),mkEmptyBT())
                 )
               )   
             )  
           
# egBSTreeN3

egBSTreeN3 = mkNodeBT(7,                                #e\label{python:egBSTreeN3}\index{egBSTreeN3@\STvar{egBSTreeN3}|STmainEntry}
               mkNodeBT(3,
                 mkNodeBT(1,
                   mkNodeBT(0,mkEmptyBT(),mkEmptyBT()),
                   mkNodeBT(2,mkEmptyBT(),mkEmptyBT())
                 ),
                 mkNodeBT(5,
                   mkEmptyBT(),
                   mkNodeBT(6,mkEmptyBT(),mkEmptyBT())
                 )
               ),
               mkNodeBT(11,
                 mkEmptyBT(),
                 mkNodeBT(13,
                   mkNodeBT(12,mkEmptyBT(),mkEmptyBT()),
                   mkNodeBT(14,mkEmptyBT(),mkEmptyBT())
                 )
               )   
             )  
           
# Tree Traversals

# Tree Traversals --- Depth First

def inOrderBT(t) :                                     #e\label{python:inOrderBT}\index{inOrderBT@\STvar{inOrderBT}|STmainEntry}
  if isEmptyBT(t) :
    return []
  else :
    return (inOrderBT(getLeftBT(t)) + [getDataBT(t)] 
            + inOrderBT(getRightBT(t))) 

def preOrderBT(t) :                                    #e\label{python:preOrderBT}\index{preOrderBT@\STvar{preOrderBT}|STmainEntry}
  if isEmptyBT(t) :
    return []
  else :
    return ([getDataBT(t)] + preOrderBT(getLeftBT(t)) 
            + preOrderBT(getRightBT(t))) 

def postOrderBT(t) :                                   #e\label{python:postOrderBT}\index{postOrderBT@\STvar{postOrderBT}|STmainEntry}
  if isEmptyBT(t) :
    return []
  else :
    return (postOrderBT(getLeftBT(t)) 
            + postOrderBT(getRightBT(t)) + [getDataBT(t)]) 

# Iterative Binary Tree Traversals
# Based on \url{http://stackoverflow.com/questions/2116662/help-me-understand-inorder-traversal-without-using-recursion} 

def inOrderBT0(t) :                                    #e\label{python:inOrderBT0}\index{inOrderBT0@\STvar{inOrderBT0}|STmainEntry}
  result = []
  if not isEmptyBT(t) :
    result = result + (inOrderBT0(getLeftBT(t)))
    result.append(getDataBT(t))
    result = result + (inOrderBT0(getRightBT(t)))
  return result

def inOrderIterBT1(t) :                                #e\label{python:inOrderIterBT1}\index{inOrderIterBT1@\STvar{inOrderIterBT1}|STmainEntry}
  result = []
  while not isEmptyBT(t) :
    result = result + (inOrderIterBT1(getLeftBT(t)))
    result.append(getDataBT(t))
    t = getRightBT(t)
  return result

def inOrderIterBT2(t) :                                #e\label{python:inOrderBT2}\index{inOrderBT2@\STvar{inOrderBT2}|STmainEntry}
  result = []
  stack = []
  while (not (stack == []) or not isEmptyBT(t)) :
    if not isEmptyBT(t) :
      stack.append(t)
      t = getLeftBT(t)
    else:
      t = stack.pop()
      result.append(getDataBT(t))
      t = getRightBT(t)
  return result

def preOrderBT0(t) :                                   #e\label{python:preOrderBT0}\index{preOrderBT0@\STvar{preOrderBT0}|STmainEntry}
  result = []
  if not isEmptyBT(t) :
    result.append(getDataBT(t))
    result = result + (preOrderBT0(getLeftBT(t)))
    result = result + (preOrderBT0(getRightBT(t)))
  return result

def preOrderIterBT1(t) :                               #e\label{python:preOrderIterBT1}\index{preOrderIterBT1@\STvar{preOrderIterBT1}|STmainEntry}
  result = []
  while not isEmptyBT(t) :
    result.append(getDataBT(t))
    result = result + (preOrderIterBT1(getLeftBT(t)))
    t = getRightBT(t)
  return result

def preOrderIterBT2(t) :                               #e\label{python:preOrderIterBT2}\index{preOrderIterBT2@\STvar{preOrderIterBT2}|STmainEntry}
  result = []
  stack = []
  while (not (stack == []) or not isEmptyBT(t)) :
    if not isEmptyBT(t) :
      result.append(getDataBT(t))
      stack.append(t)
      t = getLeftBT(t)
    else : 
      t = stack.pop()
      t = getRightBT(t)
  return result

def postOrderBT0(t) :                                  #e\label{python:postOrderBT0}\index{postOrderBT0@\STvar{postOrderBT0}|STmainEntry}
  result = []
  if not isEmptyBT(t) :
    result = result + (postOrderBT0(getLeftBT(t)))
    result = result + (postOrderBT0(getRightBT(t)))
    result.append(getDataBT(t))
  return result

def postOrderIterBT1(t) :                              #e\label{python:postOrderIterBT1}\index{postOrderIterBT1@\STvar{postOrderIterBT1}|STmainEntry}
  result = []
  if isEmptyBT(t) :
    return result
  stack = []
  while not (stack == []) or (not isEmptyBT(t)) :
    while not isEmptyBT(t) :
      if not isEmptyBT(getRightBT(t)) :
        stack.append(getRightBT(t))
      stack.append(t)
      t = getLeftBT(t)
    t = stack.pop() 
    if ((not isEmptyBT(getRightBT(t))) 
        and (stack != [] and stack[-1] is getRightBT(t))) :
      tr = stack.pop()
      stack.append(t)
      t = getRightBT(t)
    else :
      result.append(getDataBT(t))
      t = EmptyBT()  # To avoid infinite loop - it is t.rightBT
  return result

# Tree Traversals --- Depth First

# Breadth First Traversal 01
# Zipping together level orders and then flattening the result

def levelOrderBT(t : Tree) -> [[T]] :                      #e\label{python:levelOrderBT}\index{levelOrderBT@\STvar{levelOrderBT}|STmainEntry}
  if isEmptyBT(t) :                                        #e\label{python:levelOrderBTa}
    return []
  else :                                                   #e\label{python:levelOrderBTb}
    x = getDataBT(t)
    left = getLeftBT(t)
    right = getRightBT(t)
    return ([[x]] + 
      longZipMerge(levelOrderBT(left),levelOrderBT(right)))
    
def longZipMerge(xss : [[T]],yss : [[T]]) -> [[T]] :       #e\label{python:longZipMerge}\index{longZipMerge@\STvar{longZipMerge}|STmainEntry}
  if xss == [] :                                           #e\label{python:longZipMergea}
    return yss
  elif yss == [] :                                         #e\label{python:longZipMergeb}
    return xss
  else :                                                   #e\label{python:longZipMergec}
    return ([xss[0] + yss[0]] + longZipMerge(xss[1:],yss[1:]))

# AnPython3>>> levelOrderBT(egBSTree)
# [['H'], ['D', 'L'], ['B', 'F', 'J', 'N'], ['A', 'C', 'E', 'G', 'I', 'K', 'M', 'O']]
# AnPython3>>> levelOrderBT(egBSTreeN)
# [[7], [3, 11], [1, 5, 9, 13], [0, 2, 4, 6, 8, 10, 12, 14]]

# Flatten List of Lists generated by levelOrderBT(t)
# Uses list comprehensions (described elsewhere)

def flattenLevels(levels : [[T]]) -> [T] :                 #e\label{python:flattenLevels}\index{flattenLevels@\STvar{flattenLevels}|STmainEntry}
  return ([elem for level in levels for elem in level])

def breadthBT01(t : Tree) -> [T] :                          #e\label{python:breadthBT01}\index{breadthBT01@\STvar{breadthBT01}|STmainEntry}
  return flattenLevels(levelOrderBT(t))

# Example error version
# levelOrder01() does not generate an error but gives the wrong output 
# Trace a sample output
# Notice that the type declaration is valid but wrong

def levelOrderBT01(t : Tree) -> [[T]] :               #e\label{python:levelOrderBT01}\index{levelOrderBT01@\STvar{levelOrderBT01}|STmainEntry}
  if isEmptyBT(t) :                                   #e\label{python:levelOrderBT01a}
    return []
  else :                                              #e\label{python:levelOrderBT01b}
    x = getDataBT(t)
    left = getLeftBT(t)
    right = getRightBT(t)
    return ([x] +
      longZipMerge01(levelOrderBT01(left),levelOrderBT01(right)))
    
def longZipMerge01(xss : [[T]],yss : [[T]]) -> [[T]] :     #e\label{python:longZipMerge01}\index{longZipMerge01@\STvar{longZipMerge01}|STmainEntry}
  if xss == [] :                                           #e\label{python:longZipMerge01a}
    return yss
  elif yss == [] :                                         #e\label{python:longZipMerge01b}
    return xss
  else :                                                   #e\label{python:longZipMerge01c}
    return ([xss[0],yss[0]] + longZipMerge01(xss[1:],yss[1:]))

# AnPython3>>> levelOrderBT01(egBSTree)
# ['H', 'D', 'L', 'B', 'J', 'F', 'N', 'A', 'I', 'E', 'M', 'C', 'K', 'G', 'O']
# AnPython3>>> levelOrderBT01(egBSTreeN)
# [7, 3, 11, 1, 9, 5, 13, 0, 8, 4, 12, 2, 10, 6, 14]

# flattenLevels version using nested loops

def flattenLevelsA(levels : [[T]]) -> [T] :
  accumList = []
  for level in levels :
    for elem in level :
      accumList = accumList + [elem]
  return accumList


# Breadth First Traversal 02
# Enqueueing trees to be visited

def breadthBT02(t : Tree) -> [T] :                         #e\label{python:breadthBT02}\index{breadthBT02@\STvar{breadthBT02}|STmainEntry}
  return bfTraverse([],[t])

def bfTraverse(vs : [T],ts : [Tree]) -> [T] :              #e\label{python:bfTraverse}\index[pythonCode]{bfTraverse@\STvar{bfTraverse}}
  if ts == []:
    return vs
  elif isEmptyBT(ts[0]):
    return bfTraverse(vs,ts[1:])
  else:
    return (bfTraverse(vs + [getDataBT(ts[0])],
                ts[1:] + [getLeftBT(ts[0]),getRightBT(ts[0])])) 

def breadthBT03(t : Tree) -> [T] :                         #e\label{python:breadthBT03}\index{breadthBT03@\STvar{breadthBT03}|STmainEntry}
  return lbfBT([t])

def lbfBT(ts : [Tree]) -> [T] :                            #e\label{python:lbfBT}\index[pythonCode]{lbfBT@\STvar{lbfBT}}
  if ts == []:
    return []
  elif isEmptyBT(ts[0]):
    return lbfBT(ts[1:]) 
  else:
    return ([getDataBT(ts[0])] 
        + lbfBT(ts[1:] + [getLeftBT(ts[0]),getRightBT(ts[0])])) 

# Breadth First Version 04

def breadthBT04(t : Tree) -> [T] :                         #e\label{python:breadthBT04}\index[pythonCode]{breadthBT04@\STvar{breadthBT04}|STmainEntry}
  ts = [t] # Trees to visit
  vs = []  # Values seen
  while (ts != []) :
    if not (isEmptyBT(ts[0])) :
      vs = vs + [getDataBT(ts[0])]
      ts = ts[1:] + [getLeftBT(ts[0]),getRightBT(ts[0])]
    else :
      ts = ts[1:]
  return vs


# There is an error in the following version --- what is the error ?
# Why would the print statements not help ?
# Why doesn't the Python type annotations help ?

def breadthBT04A(t : Tree) -> [T] :                         #e\label{python:breadthBT04A}\index[pythonCode]{breadthBT04A@\STvar{breadthBT04A}}
  ts = [t] # Trees to visit
  vs = []  # Values seen
  while not (isEmptyBT(ts)) :
    print('ts = ',ts)
    if not (isEmptyBT(ts[0])) :
      print('len(ts) = ',len(ts))
      print('getDataBT(ts[0]) = ',getDataBT(ts[0]))
      vs = vs + [getDataBT(ts[0])]
      ts = ts[1:] + [getLeftBT(ts[0]),getRightBT(ts[0])]
    else :
      print('ts[0] is empty','len(ts) = ',len(ts))
      ts = ts[1:]
  return vs

# Binary Search Trees

# Uses the Binary Tree constructors, Inspectors and Destructors

# BST Operations

def insertBST(x,t):                                   #e\label{python:insertBST}\index{insertBST@\STvar{insertBST}|STmainEntry}
  if isEmptyBT(t):                                    #e\label{python:insertBST1}
    return mkNodeBT(x,mkEmptyBT(),mkEmptyBT()) 
  else:
    y = getDataBT(t)
    if x < y:                                         #e\label{python:insertBST2a}
      return mkNodeBT(y,insertBST(x,getLeftBT(t)),getRightBT(t)) 
    elif x > y:                                       #e\label{python:insertBST2b}
      return mkNodeBT(y,getLeftBT(t),insertBST(x,getRightBT(t))) 
    else:                                             #e\label{python:insertBST2c}
      return t

def inBST(k,t):                                       #e\label{python:inBSTree}\index{inBSTree@\STvar{inBSTree}|STmainEntry}
  if isEmptyBT():
    return False
  else:
    p = getDataBT(t)
    if k < p:                                         
      return inBST(k,getLeftBT(t)) 
    elif k > p:                                       
      return inBST(k,getRightBT(t))
    else:                                             
      return True

def isBSTree(t):                                      #e\label{python:isBSTree}\index{isBSTree@\STvar{isBSTree}|STmainEntry}
  return orderedList(inOrderBT(t)) 

def orderedList(xs):
  return (len(xs) <= 1 
          or (xs[0] < xs[1] and orderedList(xs[1:])))

def insertListBST(xs,t) :                              #e\label{python:insertListBST}\index{insertListBST@\STvar{insertListBST}|STmainEntry}
  if xs == [] :
    return t
  else :
    return insertListBST (xs[1:], insertBST(xs[0],t))


# Building a BST  

def buildBST(xs) :                                     #e\label{python:buildBST}\index{buildBST@\STvar{buildBST}|STmainEntry}
  return bBST(mkEmptyBT(), sorted(xs))


def bBST(t,xs) :
  if xs == [] :
    return t
  else :
    half = len(xs) // 2  
    x = xs[half]
    frontxs = xs[:half]
    backxs = xs[half+1:] 
    if isEmptyBT(t) :
      return (mkNodeBT(x, 
                bBST(EmptyBT(),frontxs), 
                bBST(EmptyBT(),backxs)))
    else : 
      errMsg = ("bBST: Trying to insert" + str(xs) 
               + " into nonempty tree" + str(t)) 
      raise RuntimeError(errMsg)      

# Deleting an Item from a BST

def deleteBST(x, t):                                  #e\label{python:deleteBST}\index{deleteBST@\STvar{deleteBST}|STmainEntry}
  if isEmptyBT(t):                                    #e\label{python:deleteBSTa}
    return mkEmptyBT()
  else:                                               #e\label{python:deleteBSTb}
    y = getDataBT(t)
    leftT = getLeftBT(t)
    rightT = getRightBT(t)
    if x < y:                                         #e\label{python:deleteBSTba}
      return mkNodeBT(y, (deleteBST(x,leftT)), rightT)
    elif x > y:                                       #e\label{python:deleteBSTbb}
      return mkNodeBT(y, leftT, (deleteBST(x,rightT))) 
    else:                                             #e\label{python:deleteBSTbc}
      return joinBST(leftT, rightT)     

# joinBST Version 1

def joinBST1(leftT, rightT):                          #e\label{python:joinBST1}\index{joinBST1@\STvar{joinBST1}|STmainEntry}
  if isEmptyBT(leftT):
    return rightT
  else: 
    return (insertListBST(inOrderBT(leftT), rightT))
  
# Example usage of JoinBST1

delBSTreeJoin1 = joinBST1(egBSTreeLL,egBSTreeLR)

delBSTreeJoin1ans = \
  NodeBT(dataBT='F', 
    leftBT=NodeBT(dataBT='E', 
             leftBT=NodeBT(dataBT='A', 
                      leftBT=EmptyBT(), 
                      rightBT=NodeBT(dataBT='B', 
                                leftBT=EmptyBT(), 
                                rightBT=NodeBT(dataBT='C', 
                                          leftBT=EmptyBT(), 
                                          rightBT=EmptyBT()))), 
              rightBT=EmptyBT()), 
    rightBT=NodeBT(dataBT='G', 
              leftBT=EmptyBT(), 
              rightBT=EmptyBT()))

delBSTreeJoin1test = delBSTreeJoin1 == delBSTreeJoin1ans

# joinBST Version 2

def joinBST2(leftT, rightT):                          #e\label{python:joinBST2}\index{joinBST2@\STvar{joinBST2}|STmainEntry}
  if isEmptyBT(rightT):                               #e\label{python:joinBST2a}
    return leftT
  else:
    return (mkNodeBT(getDataBT(rightT),                     #e\label{python:joinBST2b}
                   joinBST2(leftT, getLeftBT(rightT)),
                   getRightBT(rightT))) 

# Example usage of joinBST2
delBSTreeJoin2 = joinBST2(egBSTreeLL,egBSTreeLR)

delBSTreeJoin2ans = NodeBT('F', 
                      NodeBT('E', 
                        NodeBT('B', 
                          NodeBT('A', EmptyBT(), EmptyBT()), 
                          NodeBT('C', EmptyBT(), EmptyBT())), 
                        EmptyBT()), 
                      NodeBT('G', EmptyBT(), EmptyBT()))

delBSTreeJoin2test = (delBSTreeJoin2 == delBSTreeJoin2ans)


# joinBST Final Version

def joinBST(leftT, rightT):                           #e\label{python:joinBST}\index{joinBST@\STvar{joinBST}|STmainEntry}
  if isEmptyBT(rightT):                               #e\label{python:joinBSTa}
    return leftT
  else:                                               #e\label{python:joinBSTb}
    (y,t) = splitBST(rightT)
    return mkNodeBT(y, leftT, t) 


# splitBSt Version 1

def splitBST1(t):                                     #e\label{python:splitBST1}\index{splitBST1@\STvar{splitBST1}|STmainEntry}
  if isEmptyBT(t):
    raise RuntimeError("splitBST1 applied to EmptyBT()") 
  elif isEmptyBT(getLeftBT(t)):
    return (getDataBT(t), getRightBT(t))
  else:
    y = minItemBST(getLeftBT(t))
    return (y, mkNodeBT(getDataBT(t), 
                      deleteBST(y, getLeftBT(t)),
                      getRightBT(t)))

def minItemBST(t):                                    #e\label{python:minItemBST}\index{minItemBST@\STvar{minItemBST}|STmainEntry}
  if isEmptyBT(t):
    raise RuntimeError("minItemBST applied to EmptyBT()") 
  elif isEmptyBT(getLeftBT(t)):
    return (getDataBT(t))
  else:
    return (minItemBST(getLeftBT(t)))

# splitBST Final Version

def splitBST(t):                                      #e\label{python:splitBST}\index{splitBST@\STvar{splitBST}|STmainEntry}
  if isEmptyBT(t):                                    #e\label{python:splitBSTa}
    raise RuntimeError("splitBST applied to EmptyBT()") 
  else:                                               #e\label{python:splitBSTb}
    x = getDataBT(t)
    t1 = getLeftBT(t)
    t2 = getRightBT(t)
    if isEmptyBT(t1):                                 #e\label{python:splitBSTba}
      return (x,t2)
    else:                                             #e\label{python:splitBSTbb}
      (y,t3) = splitBST(t1)
      return (y, mkNodeBT(x, t3, t2))

# Height Balanced Trees
# AVL Trees

# AVL Tree Data Type

# from collections import namedtuple

EmptyABT = namedtuple('EmptyABT',[])                  #e\label{python:EmptyABT}\index{EmptyABT@\STvarKB{EmptyABT}|STmainEntry}

NodeABT = (namedtuple('NodeABT',                      #e\label{python:NodeABT}\index{NodeABT@\STvarKB{NodeABT}|STmainEntry} 
            ['heightABT','dataABT','leftABT','rightABT'])) 

# Tree type --- Augmented Binary Tree

# from typing import TypeVar,Union,NewType

# T = TypeVar('T')
ABTree = NewType('ABTree',Union[EmptyABT,NodeABT])

# AVL Tree Operations

def mkEmptyABT() -> ABTree :
  return EmptyABT()

def mkNodeABT(x: T,t1: ABTree,t2: ABTree) -> ABTree :      #e\label{python:makeABTree}\index{makeABTree@\STvar{makeABTree}|STmainEntry}
  h = 1 + max(getHeightABT(t1),getHeightABT(t2))
  return NodeABT(h,x,t1,t2)

def isEmptyABT(t: ABTree) -> bool :                        #e\label{python:isEmptyABT}\index{isEmptyABT@\STvar{isEmptyABT}|STmainEntry}
  return t == EmptyABT()

def getHeightABT(t: ABTree) -> int :                       #e\label{python:heightABT}\index{heightABT@\STvar{heightABT}|STmainEntry}
  if isEmptyABT(t) :
    return 0
  else:
    return t.heightABT

def getDataABT(t: ABTree) -> T :                          #e\label{python:getDataABT}\index{getDataABT@\STvar{getDataABT}|STmainEntry}
  if isEmptyABT(t) :
    raise RuntimeError("getDataABT applied to EmptyABT()") 
  else:
    return t.dataABT   

def getLeftABT(t: ABTree) -> ABTree :                      #e\label{python:getLeftABT}\index{getLeftABT@\STvar{getLeftABT}|STmainEntry}
  if isEmptyABT(t) :
    raise RuntimeError("getLeftABT applied to EmptyABT()") 
  else:
    return t.leftABT   

def getRightABT(t: ABTree) -> ABTree :                     #e\label{python:getRightABT}\index{getRightABT@\STvar{getRightABT}|STmainEntry}
  if isEmptyABT(t) :
    raise RuntimeError("getRightABT applied to EmptyABT()") 
  else:
    return t.rightABT   

# AVL Property Functions 1

def isBSABTree(t):                                    #e\label{python:isBSABTree}\index{isBSABTree@\STvar{isBSABTree}|STmainEntry}
  return orderedList(inOrderABT(t))
  
def inOrderABT(t):                                    #e\label{python:inOrderABT}\index{inOrderABT@\STvar{inOrderABT}|STmainEntry}
  if isEmptyABT(t):
    return []
  else:
    return (inOrderABT(getLeftABT(t)) + [getDataABT(t)]
            + inOrderABT(getRightABT(t)))

# AVL Property Functions 2

def balFactorABT(t):                                  #e\label{python:balFactorABT}\index{balFactorABT@\STvar{balFactorABT}|STmainEntry}
  if isEmptyABT(t):
    return 0
  else:
    return (getHeightABT(getLeftABT(t)) 
            - getHeightABT(getRightABT(t)))

# hasAVLpropABT

def hasAVLpropABT(t):                                 #e\label{python:hasAVLpropABT}\index{hasAVLpropABT@\STvar{hasAVLpropABT}|STmainEntry}
  if isEmptyABT(t):
    return True
  else:
    return (abs(balFactorABT(t)) <= 1
            and hasAVLpropABT(getLeftABT(t)) 
            and hasAVLpropABT(getRightABT(t)))
# isAVLABTree

def isAVLABTree(t):                                   #e\label{python:isAVLABTree}\index{isAVLABTree@\STvar{isAVLABTree}|STmainEntry}
  return (isBSABTree(t) and hasAVLpropABT(t))

# Converting BinTree to ABinTree

def convertBTtoABT(t):                               #e\label{python:convertABtoABT}\index{convertABtoABT@\STvar{convertABtoABT}|STmainEntry}
  if isEmptyBT(t):
    return EmptyABT()
  else:
    leftABT = convertBTtoABT(getLeftBT(t))
    rightABT = convertBTtoABT(getRightBT(t))
    return makeABTree(getDataBT(t), leftABT, rightABT)

# The Rotate Functions
# They assume the input has appropriate nonempty subtrees

def rotr(t):                                          #e\label{python:rotr}\index{rotr@\STvar{rotr}|STmainEntry}
  k = getDataABT(t)
  kL = getDataABT(getLeftABT(t))
  leftLeftT = getLeftABT(getLeftABT(t))
  leftRightT = getRightABT(getLeftABT(t))
  rightT = getRightABT(t)
  return (mkNodeABT(kL, 
                     leftLeftT, 
                     mkNodeABT(k, leftRightT, rightT)))

def rotl(t):                                          #e\label{python:rotl}\index{rotl@\STvar{rotl}|STmainEntry}
  k = getDataABT(t)
  kR = getDataABT(getRightABT(t))
  rightLeftT = getLeftABT(getRightABT(t))
  rightRightT = getRightABT(getRightABT(t))
  leftT = t.leftABT
  return (mkNodeABT(kR, 
                     mkNodeABT(k, leftT, rightLeftT), 
                     rightRightT))

# makeAVLTree Function

def makeAVLTree(x, leftT, rightT):                    #e\label{python:makeAVLTree}\index{makeAVLTree@\STvar{makeAVLTree}|STmainEntry}
  hL = getHeightABT(leftT)
  hR = getHeightABT(rightT)
  if (hR + 1 < hL) and (balFactorABT(leftT) >= 0):
    return rotr(mkNodeABT(x, leftT, rightT))
  elif (hR + 1 < hL):
    return rotr(mkNodeABT(x, (rotl(leftT)),rightT))
  elif (hL + 1 < hR) and (balFactorABT(rightT) > 0):
    return rotl(mkNodeABT(x, leftT, rotr(rightT))) 
  elif (hL + 1 < hR):
    return rotl(mkNodeABT(x, leftT, rightT))
  else:
    return mkNodeABT(x, leftT, rightT)

# insertAVLT and deleteAVLT Functions

def insertAVLT(x,t):                                  #e\label{python:insertAVLT}\index{insertAVLT@\STvar{insertAVLT}|STmainEntry}
  if isEmptyABT(t):
    return mkNodeABT(x, mkEmptyABT(), mkEmptyABT())
  else:
    y = getDataABT(t)
    leftT = getLeftABT(t)
    rightT = getRightABT(t)
    if x < y:
      return makeAVLTree(y, insertAVLT(x, leftT), rightT) 
    elif x > y:
      return makeAVLTree(y, leftT, insertAVLT(x, rightT)) 
    else:
      return t

def insertListAVLT(xs,t):                             #e\label{python:insertListAVLT}\index{insertListAVLT@\STvar{insertListAVLT}|STmainEntry}
  if xs == []:
    return t
  else:
    return insertListAVLT(xs[1:], (insertAVLT(xs[0],t))) 

def deleteAVLT(x,t):                                  #e\label{python:deleteAVLT}\index{deleteAVLT@\STvar{deleteAVLT}|STmainEntry}
  if isEmptyABT(t):
    return mkEmptyABT()
  else:
    y = getDataABT(t)
    leftT = getLeftABT(t)
    rightT = getRightABT(t)
    if x < y:
      return makeAVLTree(y, deleteAVLT(x, leftT), rightT) 
    elif x > y:
      return makeAVLTree(y, leftT, deleteAVLT(x, rightT)) 
    else:
      return joinAVLT(leftT, rightT)

# joinAVLT 

def joinAVLT(leftT, rightT):                          #e\label{python:joinAVLT}\index{joinAVLT@\STvar{joinAVLT}|STmainEntry}
  if isEmptyABT(rightT):
    return leftT
  else:
    (y,t) = splitAVLT(rightT)
    return makeAVLTree(y, leftT, t) 

# splitAVLT 

def splitAVLT(t):                                     #e\label{python:splitAVLT}\index{splitAVLT@\STvar{splitAVLT}|STmainEntry}
  if isEmptyABT(t):
    raise RuntimeError("splitAVLT applied to EmptyABT()") 
  else:
    x = getDataABT(t)
    t1 = getLeftABT(t)
    t2 = getRightABT(t)
    if isEmptyABT(t1):
      return (x,t2)
    else:
      (y,t3) = splitAVLT(t1)
      return (y, makeAVLTree(x, t3, t2))



# V0.1 2022/11/08 Based on previous M269 notes