from anytree import Node, RenderTree
from anytree.exporter import UniqueDotExporter

def Inorder(root):
	"""
	Perform an inorder traversal of a tree and print the nodes values
	Ignores the ~ (not) symbol

	Args:
		root (TreeNode): The root node of the tree.

	Returns:
		None
	"""
	if root.is_leaf:
		# If the current node is a leaf node, print its name
		print(root.name, end="")

	if root.children:
		# If the current node has children, recursively traverse them
		left = root.children[0]
		right = root.children[1]
		print("(", end="")
		Inorder(left)
		print(root.name, end="")
		Inorder(right)
		print(")", end="")


def Inorder1(root):
	"""
	Inorder, polish notation(?)
	
	Args:
		root (TreeNode): The root node of the tree.
	
	Returns:
		None
	"""
	if root is None:
		return

	if (root.children):
		left = root.children[0]
		right = root.children[1]
		print("(", end="")
		Inorder1(left)
		Inorder1(right)
		print(")", end="")

	print(root.name, end="")

def Inorder2(root):
	"""
	Regular inorder traversal of a tree.

	Args:
		root (TreeNode): The root node of the tree.

	Returns:
	None
	"""
	if root.is_leaf:
		print(root.name, end="")
		
	if root.name == "~" and root.children:
		child = root.children[0]
		print("~", end="")
		Inorder2(child)
	elif (root.children):
		left = root.children[0]
		right = root.children[1]
		print("(", end="")
		Inorder2(left)
		print(root.name, end="")
		Inorder2(right)
		print(")", end="")

# Tree without not
sroot = Node("<->")
sl0 = Node("->", parent=sroot)
sr0 = Node("->", parent=sroot)
sl0l = Node("p", parent=sl0)
sl0r = Node("q", parent=sl0)
sr0le = Node("~p", parent=sr0)
sr0re = Node("~q", parent=sr0)

Inorder(sroot)
print()

Inorder1(sroot)
print()

# Tree with not
# ((p->q)<->(~p)->(~q))
root = Node("<->")
l0 = Node("->", parent=root)
r0 = Node("->", parent=root)
l0l = Node("p", parent=l0)
l0r = Node("q", parent=l0)
r0l = Node("~", parent=r0)
r0le = Node("p", parent=r0l)
r0r = Node("~", parent=r0)
r0re = Node("q", parent=r0r)

UniqueDotExporter(root).to_picture("tree.png")

Inorder2(root)
print()

# Another tree with not from book, page 9
# p->(q<->~(p->~q))
zroot = Node("->")
zl = Node("p", parent=zroot)
zr = Node("<->", parent=zroot)
zrl = Node("q", parent=zr)
zrr = Node("~", parent=zr)
zrrb = Node("->", parent=zrr)
zrrl = Node("p", parent=zrrb)
zrrr = Node("~", parent=zrrb)
zrrrb = Node("q", parent=zrrr)

UniqueDotExporter(zroot).to_picture("tree1.png")

Inorder2(zroot)
print()