//************************************************************//
//********* Intro. to Trees - January 27th, 2017*************//
//**********************************************************//

-Well, we've gone through "Don't Stop Me Now" and are on to the MJ tracks...this show needs to get on the road
------------------------------------------------

-So, Linked Lists, Stacks, Queues...they're nice, sure, but TREES are where data structures get real
    -All of these other data structures have been linear; trees can go in multiple directions
        -*technically you can imagine the other structures as 1D trees, but that's just getting cheeky
    -Their fundamental idea: how to move through information
-REMEMBER: Trees are a SET of data structures, with many types of sub-trees (binary trees, BST's (WHICH ARE NOT JUST BINARY TREES), AVL trees, etc.)

-So, in CS, a TREE is "an abstract model of a hierarchal structure"; they're an ADT that consists of nodes with a parent-child relationship
    -By this definition, a Linked List is *technically* a tree
-Trees are "limited graphs"; aka, they have NO cycles; they have a fundamentally recursive structure (i.e. branching)
-Some applications:
    -File Systems
    -Organization charts
    -Anything your puny mind can imagine!

                |
                /\
               /  \
              /    \
             /\    /\ (...it's too hard to draw an ASCII tree :/ )

-In this class, FOR OUR PURPOSES, we will assume there are no duplicate nodes in a tree when dealing with non-numerical data (when dealing with integers, though...wellllll...)

-IMPORTANT TERMS:
    -ROOT NODE:
        -The node where you enter the tree; it does NOT have a parent, and is almost always on the top of the tree
    -INTERNAL NODES:
        -A node with at least one child node
    -LEAF NODES (aka "External" nodes):
        -Nodes with no children; usually at the bottom of a branch
    -PARENT (of a node):
        -Node immediately above another node
    -ANCESTOR NODES:
        -All of the parents, grand-parent, great-grandparents, etc.,, of a node
    -CHILDREN (of a node):
        -The node(s) IMMEDIATELY below a node (just 1 level down)
    -DESCENDANTS (of a node):
        -The children, grandchildren, great-grandchiltren, etc. of a node
    -"Height" (of a node):
        -The # of nodes that need to be traversed to reach a leaf node/the end of a branch; in this class, we count from "bottom-up," so the height of a leaf node is 0
            -If an internal node has a child that's a leaf, but a non-leaf child, then we count the height as if it's counting up from the non-leaf child (aka, always takes the higher #)
    -"Depth" (of a node):
        -The reverse of height, this is how many nodes you need to go up to reach the root node. IN THIS CLASS, THE "DEPTH" OF THE ROOT NODE IS 1 (yes, 1, NOT 0!!!); we count from "top-down"
            -Depth is the "level" of the tree; height talks about "what's below me?" for a node
    -SUBTREE:
        -A tree within the tree consisting of a node and its descendants
            -Can be any possible subtree within the tree (including the original tree, which is technically a "subtree" of itself)

-So, what methods will you find in pretty much EVERY tree?
    -Generic methods:
        -int size(): returns the size of the tree
        -boolean isEmpty()
        -Iterator iterator():
        -Iterable positions()"

    -Accessor methods (getting a node):
        -position root():
        -positions parent(p):
        -Iterable children(p):
        -int numChildren(p):

    -Query methods (get infrmation about the node):
        -boolean isExternal(p):
        -boolean isInternal(p):
        -boolean isRoot(p):

-NOTE: Trees are recursive data structures due to the way they "branch"; because of this, basically EVERY operation done on the tree (searching, adding, removing, etc.) is handled as a recursive method; while it is SOMETIMES possible to do this iteratively, usually these implementations are messier, more error-prone, and often more inefficient than just writing it recursively

-BINARY TREES are an ADT type of tree where each node has AT MOST 2 children (a left/right child)
    -Can think of the children as an "ordered pair"
    -A binary tree contains a single root node with an ordered pair of children (which are themselves the root nodes of binary sub-trees)
-Applications:

-Some notation: n = # of nodes; e = # of external nodes; i = # of internal nodes; h = height
-BT Properties:
    -e = i + 1
    -h <= i
    -n = 2e - 1
    -e <= 2^h
    -h <= (n-1) / 2

-BT's inherit all of the methods of a normal Tree ADT, but also has three methods for each node:
    -position left(p)
    -position right(p)
    -position sibling(p)

-A BINARY SEARCH TREE is a special case of a Binary Tree, where the LEFT CHILD is ALWAYS smaller than the parent node, and the RIGHT CHILD is ALWAYS LARGER than the parent node
    -What happens to equal items? Well, that depends on the implementation
-So, the left subtree contains ONLY items smaller than the root node, and the right subtree contains ONLY items larger than the root node
    -You might ask, "well, what if we end up with a tree where everything is on one side? Wouldn't that be inefficient, since its basically just a linked list then? Could we fix that problem?" Just you wait...
-A BST is "BALANCED" when all of its leaf nodes (or at least as many as possible) are on the same level
    -In general, BST's can be REALLY out of whack and unbalanced without too many problems

-TREE TRAVERSALS-
    -A TRAVERSAL visits all of a tree's nodes in a systematic order
    -For ALL trees, you can perform a "pre-order traversal" (visit node, then visit all of the left children, then visit all of the right children), a "post-order traversal" (), and a "level traversal"
        -"Pre" because you visit ALL of the left-most nodes first, "post" because you visit ALL of the right-most nodes first...
        -Level traversals just go down row-by-row (breadth-first search?)

-We'll talk about this in more detail on Monday!