#!/usr/bin/env python3

# Binary Tree Python code for M269 from 2021J
# Written by Phil Molyneux
# Based on m269_tree.py
# Versions (see end)
# 


class Tree :
  
  def __init__(self) :
    self.root = None
    self.left = None
    self.right = None
    
def is_empty(tree) :
  return (tree.root == tree.left == tree.right == None)
  
def join(item, left, right) :
  tree = Tree()
  tree.root = item
  tree.left = left
  tree.right  = right
  return tree

def is_leaf(tree) :
  return (not is_empty(tree) and is_empty(tree.left) and is_empty(tree.right))

def size(tree) :
  if is_empty(tree) :
    return 0
  else :
    return (size(tree.left) + size(tree.right) + 1)

def height(tree) :
  if is_empty(tree) :
    return 0
  else :
    return (max(height(tree.left), height(tree.right)) + 1)

# Binary Tree Traversals
# 
# Depth First
# 
# Pre-order traversal

def has(tree, item) :
  if is_empty(tree) :
    return False
  elif tree.root == item :
    return True
  else :
    return (has(tree.left, item) or has(tree.right, item))

# Sample Trees

EMPTY = Tree()
THREE = join(3, EMPTY, EMPTY)
FOUR = join(4, EMPTY, EMPTY)
FIVE = join(5, EMPTY, EMPTY)
SIX = join(6, EMPTY, EMPTY)

TPM = join('*', join('+', THREE, FOUR), join('-', FIVE, SIX)) 
      # (3+4)*(5-6)
PMT = join('+', THREE, join('-', join('*', FOUR, FIVE), SIX)) 
      # 3+((4*5)-6)
MPT = join('-', join('+', THREE, join('*', FOUR, FIVE)), SIX) 
      # (3+(4*5))-6


# Tree traversals

# Pre-order traversal

def has(tree,item) :
  if is_empty(tree) :
    return false
  elif tree.root == item :   # visit a node
    return true
  else :
    return has(tree.left, item) or has(tree.right, item)
    
# The general pattern

def preOrderBT(t):                                    
  if isEmptyBT(t):
    return []
  else:
    return ([t.dataBT] + preOrderBT(t.leftBT) 
            + preOrderBT(t.rightBT)) 


# In-order traversal

def infix(exprBT) :
  """Return fully bracketed string representation of expression"""
  result = ''
  if is_empty(exprBT) :
    return result
  else :
    result = (result + '(')
    result = (result + infix(exprBT.left))
    result = (result + (' ' + str(exprBT.root) + ' '))
    result = (result + infix(exprBT.right))
    result = (result + ')')
    return result

# The general pattern

def inOrderBT(t):                                    
  if is_emptyBT(t):
    return []
  else:
    return (inOrderBT(t.left) + [t.root] 
            + inOrderBT(t.right)) 

# Infix tests

MTP = join('-', join('*', join('+', THREE, FOUR), FIVE), SIX)

def testInfix01() :
  print("MTP = " + infix(MTP))  # ((3+4)*5)–6
  print()
  print("TPM = " + infix(TPM))  # (3+4)*(5-6)
  print()
  print("PMT = " + infix(PMT))  # 3+((4*5)-6)
  print()
  print("MPT = " + infix(MPT))  # (3+(4*5))-6
  

# In-order traversal

def evalExprBT(exprBT) :
  """Return the value of the expression tree.
     
  Preconditions:
  - expression isn't empty
  - expression only has operators +, -, * and numeric operands
  """
  if is_leaf(exprBT):
    return exprBT.root
  leftValue = evalExprBT(exprBT.left)
  rightValue = evalExprBT(exprBT.right)
  operator = exprBT.root
  if operator == '+' :
    return leftValue + rightValue
  elif operator == '-' :
    return leftValue - rightValue
  elif operator == '*' :
    return leftValue * rightValue
  

# General pattern

def postOrderBT(t):                                   
  if isEmptyBT(t):
    return []
  else:
    return (postOrderBT(t.leftBT) 
            + postOrderBT(t.rightBT) + [t.dataBT]) 

# evalExprBT tests

def testEvalExprBT() :
  print("MTP = " + infix(MTP))                  # ((3+4)*5)–6
  print(' =', evalExprBT(MTP))
  print("TPM = " + infix(TPM))                  # (3+4)*(5-6)
  print(' =', evalExprBT(TPM))
  print("PMT = " + infix(PMT))                  # 3+((4*5)-6)
  print(' =', evalExprBT(PMT))
  print("MPT = " + infix(MPT))                  # (3+(4*5))-6
  print(' =', evalExprBT(MPT))
  


# Versions
# V0.1 2022/01/18 Based on m269_tree.py