# Trees
What is the root of a tree?
What is a binary tree, a tenary tree, n-ary tree, or simply, a tree?

We will be implementing a binary tree
    
        node
       /    \
   node      node
  /   \      /   \
node  node node node


Each node consists of three attributes:
.value : given when initializing the node
.left  : initializes as None
.right : initializes as None

class Node:
  def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None

# Creating a binary tree

root0 = Node(3)
root0.left = Node(1)
root0.right = Node(2)
root0.left.left = Node(3)
root0.left.right = Node(4)
root0.right.left = Node(5)
root0.right.right = Node(3)
      3
    /   \
   1     2
  / \   / \
 3   4 5   3

# Creating another binary tree

root1 = Node("a")
root1.left = Node("b")
root1.right = Node("e")
root1.left.left = Node("c")
root1.left.right = Node("d")
#      a
#    /   \
#   b     e
#  / \
# c   d

# TODO: Create this binary tree: root2

#    z
#  /   \
# w     y
#      /
#     x

## Key insight

'''
Since a binary tree starts from a root
and branches left and right,
we observe that each left and right nodes are also "sub-trees"

That is to say,
a tree is made out of many smaller trees.

This makes most tree problems easily solved via recursion.
'''

# Basic Tree Problems

NOTE: In the following problems, the tree parameter represents a single tree node.
The initial call to the function (in our test code) passes the root node of the tree.

def size(tree):
    ''' Return the total number of nodes in the tree '''
    if tree is None:
        return 0
    else:
        return 1 + size(tree.left) + size(tree.right)
  
def total(tree):
    '''
    Return the total sum of all values in the tree
    Assumes integer values only
    '''
    if tree is None:
        return 0
    else:
        return tree.value + total(tree.right) + total(tree.left)

  pass

def contains(tree, x):
    ''' Return True if the value x is contained in tree, False otherwise '''
    if tree is None:
        return False
    elif tree.value === x:
        return True
    else:
        return contains(tree.left, x) or contains(tree.right, x)
        

def count(tree, x):
    ''' Return the number of occurrences of x tree '''
    if tree is None:
        return 0
    else
        acc = count(tree.left, x) + count(tree.right,x)
        if tree.value === x:
            acc += 1
        return acc

# (Extra) More Tree Problems

def largest(tree):
    ''' Return the largest value in the tree '''
    if tree is None:
        return float('-inf')
    
    return max(tree.value, largest(tree.left), largest(tree.right))
               
def smallest(tree):
    ''' Return the smallest value in the tree '''
    if tree is None:
        return float('inf')
    
    return min(tree.value, smallest(tree.left), smallest(tree.right))

def maximum_depth(tree):
    '''
    Return the maximum depth (number of levels) in the tree.
    Root node counts as 1 level.
    '''
    if tree is None:
        return 0
    return 1 + max(maximum_depth(tree.right), maximum_depth(tree.left))

# What is a leaf node? nodes that have no children
def count_leaves(tree):
    ''' Return the total number of leaf nodes in the tree '''
    if tree is None:
        return 0
    elif tree.left == None and tree.right == None:
        return 1
    else: 
        return count_leaves(tree.left) + count_leaves(tree.right)

# What is a perfect tree? 2**n - 1 nodes, every level in tree fully filled
def is_perfect(tree):
    '''
    Return True if the binary tree is perfect, False otherwise.
    Feel free to use above functions as helper functions if helpful.
    '''    
    return count_leaves(tree) == 2 ** (maximum_depth(tree) - 1)

# Part 1

class Node:
  def __init__(self, val):
    self.value = val
    self.left = self.right = None

def create_tree(nested_list):
  ''' Helper function to create a tree '''
  if nested_list:
    root = Node(nested_list[0])
    root.left = create_tree(nested_list[1])
    root.right = create_tree(nested_list[2])
    return root

## Creating a binary tree

root0 = create_tree([0, [1, [3, [], []], [4, [], []]], [2, [5, [], []], [6, [], []]]])
      0
    /   \
   1     2
  / \   / \
 3   4 5   6

## Creating another binary tree

root1 = create_tree(['a', ['b', ['c', [], []], ['d', [], []]], ['e', [], []]])
      a
    /   \
   b     e
  / \
 c   d

## Creating yet another binary tree

root2 = create_tree(['z', ['w', [], []], ['y', ['x', [], []], []]])
      z
    /   \
   w     y
        /
       x

# TODO: Pick a traversal convention and traverse any of the example trees.

##Traversals

In tree traversals, we are interested in going through all values in a tree and extracting out the values.

There are 4 main ways to traverse through a tree, which we will go through today.

Note: Pre/In/Post-order typically uses a stack structure to traverse.
Recursion will be very helpful here,
since there is an implicit stack involved.
Level-order typically uses of a queue structure to traverse.

# Pre-order Traversal

def pre_order(tree):
  ''' Return the list of values from: root, left subtree, right subtree '''
  pass


#      a
#    /   \
#   b     e
#  / \
# c   d

print("\n=== pre_order ===")
print(pre_order(root1)) # ['a', 'b', 'c', 'd', 'e']

# In-order Traversal

def in_order(tree):
  ''' Return the list of values from: left subtree, root, right subtree '''
  # TODO: Complete in-order traversal individually
  pass

print("\n=== in_order ===")
print(in_order(root0)) # [3, 1, 4, 0, 5, 2, 6]
print(in_order(root1)) # ['c', 'b', 'd', 'a', 'e']

########################
# Post-order Traversal #
########################

def post_order(tree):
  ''' Return the list of values from: left subtree, right subtree, root '''
  # TODO: Complete post-order traversal individually
  pass

print("\n=== post_order ===")
print(post_order(root2)) # ['w', 'z', 'y', 'z']

# Level-order Traversal

def level_order(tree):
  ''' Return the list of values level by level (Hint: Consider iteration) '''
  # TODO: Discuss together, then attempt level-order traversal individually
  pass

print("\n=== level_order ===")
print(level_order(root0)) # [0, 1, 2, 3, 4, 5, 6, 7]
print(level_order(root1)) # ['a', 'b', 'e', 'c', 'd']

# (Extra) Iterative solutions

Note: These are not trivial and get increasingly difficult to understand

> https://www.geeksforgeeks.org/iterative-preorder-traversal/

def pre_order_iter(tree):
  ''' Return the list of values from: root, left subtree, right subtree '''
  pass

print("\n=== pre_order_iter ===")
print(pre_order_iter(root1)) # ['a', 'b', 'c', 'd', 'e']

> https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
>

def in_order_iter(tree):
  ''' Return the list of values from: left subtree, root, right subtree '''
  pass

print("\n=== in_order_iter ===")
print(in_order_iter(root0) == [3, 1, 4, 0, 5, 2, 6]) # True

> https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

def post_order_iter(tree):
  ''' Return the list of values from: left subtree, right subtree, root '''
  pass

print("\n=== post_order_iter ===")
print(post_order_iter(root2)) # ['w', 'z', 'y', 'z']