#!/usr/bin/env python3

# Lowest Common Ancestern 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:mkEmptyBT}\index{makeEmptyBT@\STvar{makeEmptyBT}|STmainEntry}
  return EmptyBT()

def mkNodeBT(x : T,t1 : Tree,t2 : Tree) -> Tree :            #e\label{python:mkNakeBT}\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)))

def isLeafBT(t : Tree) -> bool :                           #e\label{python:isLeafBT}\index{isLeafBT@\STvar{isLeafBT}|STmainEntry}
  return (not isEmptyBT(t) 
          and isEmptyBT(getLeftBT(t)) and isEmptyBT(getRightBT(t)))

def exposeBT(t : Tree) -> (Tree, T, Tree) :                #e\label{python:exposeBT}\index{exposeBT@\STvar{exposeBT}|STmainEntry}
  if isEmptyBT(t) :
    raise RuntimeError("exposeBT applied to EmptyBT()")
  else :
    tL = getLeftBT(t)
    k  = getDataBT(t)
    tR = getRightBT(t)
    return (tL,k,tR)

# 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())
                )
              )   
           )             


# Lowest Common Ancester Code

# Based on \href{https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/}{Lowest Common Ancestor in a Binary Tree}

def lca(t  Tree, k1: T, k2: T) -> Tree :                   #e\label{python:lca}\index{lca@\STvar{lca}|STmainEntry}
  if isEmptyBT(t) :                                        #e\label{python:lcaA}
    return mkEmptyBT()
  elif (getDataBT(t) == k1 or getDataBT(t) == k2) :        #e\label{python:lcaB}
    return t
  else :                                                   #e\label{python:lcaC}
    leftLCA  = lca(getLeftBT(t),k1,k2)
    rightLCA = lca(getRightBT(t),k1,k2)
    if (not (isEmptyBT(leftLCA))                           #e\label{python:lcaD}
        and not (isEmptyBT(rightLCA))) :
      return t
    else :                                                 #e\label{python:lcaE}
      return (leftLCA if not (isEmptyBT(leftLCA)) 
                      else rightLCA)
  
def isInTree(t: Tree, k: T) -> bool :                      #e\label{python:isInTree}\index{isInTree@\STvar{isInTree}|STmainEntry}
  if isEmptyBT(t) :
    return False
  elif (getDataBT(t) == k) :
    return True
  else :
    return (isInTree(getLeftBT(t), k) 
            or isInTree(getRightBT(t), k))


def reportLCA(t: Tree, k1: T, k2: T) -> str :              #e\label{python:reportLCA}\index{reportLCA@\STvar{reportLCA}|STmainEntry}
  if (not isInTree(t, k1) or not isInTree(t, k2)) :
    return ("Not both k1 \'" + k1 + "\' and k2 \'" 
            + k2 + "\' are in the tree")
  else :
    valueLCA = lca(t, k1, k2)
    if isEmptyBT(valueLCA) :
      return str(valueLCA)
    else :
      reportStr = ("Key value of LCA is \'" 
                   + str(getDataBT(valueLCA)) + "\'")
      return reportStr
      
# See \href{https://stackoverflow.com/questions/68074665/how-to-find-nearest-common-ancestor-class-of-two-objects}{How to find nearest common ancestor class of two objects?}
# Iterative version is in above reference
# See \href{https://en.wikipedia.org/wiki/Lowest_common_ancestor}{Wikipedia: Lowest Common Ancestor}
# See \href{https://rosettacode.org/wiki/Schieber-Vishkin_algorithm}{Rosetta Code LCA Schieber-Vishkin Algorithm}