Problem Challenge 2

from __future__ import print_function
from collections import deque
class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left, self.right = None, None
def tree_right_view(root):
  result = []
  if root is None:
    return result
  queue = deque()
  queue.append(root)
  while queue:
    levelSize = len(queue)
    for i in range(0, levelSize):
      currentNode = queue.popleft()
      # if it is the last node of this level, add it to the result
      if i == levelSize - 1:
        result.append(currentNode)
      # insert the children of current node in the queue
      if currentNode.left:
        queue.append(currentNode.left)
      if currentNode.right:
        queue.append(currentNode.right)
  return result
def main():
  root = TreeNode(12)
  root.left = TreeNode(7)
  root.right = TreeNode(1)
  root.left.left = TreeNode(9)
  root.right.left = TreeNode(10)
  root.right.right = TreeNode(5)
  root.left.left.left = TreeNode(3)
  result = tree_right_view(root)
  print("Tree right view: ")
  for node in result:
    print(str(node.val) + " ", end='')
main()

from __future__ import print_function
from collections import deque
import copy
# Display List Code Below:
def height(node):
	if (node == None):
		return 0
	return 1 + max(height(node.left), height(node.right))
def draw_node(output, link_above, node, level, p, link_char):
	if (node == None): 
 		return
	out = "["
	h = len(output)
	SP = " "
	if (p < 0):
		for s in output:
			if (s):
				s = " "*(-1*p) + s
    
		for s in link_above:
			if (s):
				s = " "*(-1*p) + s
	if level < h - 1:
		p = max(p, len(output[level + 1]))
	if (level > 0):
		p = max(p, len(output[level - 1]))
	p = max(p, len(output[level]))
	# Fill in to left
	if (node.left):
		leftData = SP + str(node.left.val) + SP
		draw_node(output, link_above, node.left, level + 1, p - len(leftData),'L')
		p = max(p, len(output[level + 1]))
	# Enter this data
	space = p - len(output[level])
	if (space > 0):
		output[level] += (' ' * space)
	node_data = SP + str(node.val) + SP
	output[level] += node_data
	# Add vertical link above
	space = p + len(SP) - len(link_above[level])
	if (space > 0):
		link_above[level] += (' ' * space)
	link_above[level] += link_char
	# Fill in to right
	if (node.right):
		draw_node(output, link_above, node.right, level + 1, len(output[level]),'R')
  
def display_tree(root):
	if (root == None):
		print("\tNone")
	h = height(root)
	output = []
	link_above = []
	for i in range(0,h): 
				output.append("")
				link_above.append("")
	draw_node(output, link_above, root, 0, 5, ' ')
	# Create link lines
	for i in range(h):
		for j in range(len(link_above[i])):
			if (link_above[i][j] != ' '):
				size = len(output[i - 1])
				if (size < j + 1):
					output[i - 1] += " " *(j + 1 - size)
				jj = j
				if (link_above[i][j] == 'L'):
					while (output[i - 1][jj] == ' '):
						jj += 1
					for k in range(j+1, jj-1):
						str1 = output[i - 1]
						list1 = list(str1)
						list1[k] = '_'
						output[i - 1] = ''.join(list1)
				elif(link_above[i][j] == 'R'):
					while (output[i - 1][jj] == ' '):
						jj-=1
					
					# k = j-1
					for k in range(j-1,jj+1,-1):
						temp = output[i - 1]
						list1 = list(temp)
						list1[k] = '_'
						output[i - 1] = ''.join(list1)
						k = k - 1
      
				str1 = link_above[i]
				list1 = list(str1)
				list1[j] = '|'
				link_above[i] = ''.join(list1)
					
	# Output
	for i in range(h):
		if (i):
			print("\t" , link_above[i])
		print("\t" , output[i])
def printq(queue):
  strqueue = "["
  for i in queue:
    strqueue += str(i.val) + ", "
  if not queue:
	  str2 = strqueue+"]"
	  return str2
  str2 = strqueue[:-2]+"]"
  return str2
class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left, self.right = None, None
def traversal(root, result):
	if root is None:
		return
	if root in result:
		root.val = str(root.val) + "*"
	traversal(root.left, result)
	traversal(root.right, result)
def tree_right_view(root):
  result = []
  if root is None:
    return result
  print("Result: ", printq(result), sep = "")
  queue = deque()
  queue.append(root)
  print("Appending root to queue: ", printq(queue), sep = "")
  print("")
  j = 1
  while queue:
    print("While loop iteration: ", j, sep = "")
    j+=1
    levelSize = len(queue)
    print("\tLength of queue --> levelSize: ", levelSize, sep = "")
    l = 1
    for i in range(0, levelSize):
      print("\t\tFor loop iteration: ", l, sep = "")
      l +=1
      tempqueue = deque()
      tempqueue = copy.copy(queue)
      currentNode = queue.popleft()
      print("\t\t\tPopping from the queue: ", printq(tempqueue), " --> ", printq(queue), sep = "")
      print("\t\t\tcurrentNode: ", currentNode.val,sep="" )
      # if it is the last node of this level, add it to the result
      if i == levelSize - 1:
        result.append(currentNode)
        print("\t\t\t", currentNode.val, " is the last node of level ", levelSize, " --> appending to result", sep = "")
        print("\t\t\tResult: ", printq(result), sep = "")
      # insert the children of current node in the queue
      if currentNode.left or currentNode.right:
        print("\t\t\tInserting children of the current node, ", currentNode.val,", in the queue", sep = "")
      else:
        print("\t\t\tCurrent node, ", currentNode.val, ", does not have any children", sep = "")
      if currentNode.left:
        queue.append(currentNode.left)
        print("\t\t\t\tAppending left child: ", printq(queue), sep = "")
      if currentNode.right:
        queue.append(currentNode.right)
        print("\t\t\t\tAppending right child: ", printq(queue),"\n", sep = "")
  return result
def main():
  root = TreeNode(12)
  root.left = TreeNode(7)
  root.right = TreeNode(1)
  root.left.left = TreeNode(9)
  root.right.left = TreeNode(10)
  root.right.right = TreeNode(5)
  root.left.left.left = TreeNode(3)
  root2 = TreeNode(14)
  root2.left = TreeNode(7)
  root2.right = TreeNode(1)
  root2.right.left = TreeNode(10)
  root2.right.right = TreeNode(5)
  input = [root, root2]
  for i in input:
      print("Input tree: ")
      display_tree(i)
      print("")
      result = tree_right_view(i)
      print("Tree right view: ")
      str_out = ""
      for node in result:
        str_out += str(node.val) + ", "
      str_out = "[" + str_out[:-2] + "]"   
      print(str_out)
      traversal(i, result)
      print("")
      display_tree(i)
      print(("-"*100)+"\n")
main()