gistfile1.txt

trees
linked data structure - most used linked lists




         * - root
               /   \
     child *      * child   ← depth 1
                   /         \
          child *           * child  ← depth 2

Tree can have several levels, all the nodes that exist at the same distance from the root are comprise a level.  The depth of a node is equal to the distance from the root.

Tree has a height - this is equal to the length of the longest path from the root to the lowest node.

key terms - depth, node, tree, height
empty tree is -1 height
single node tree height is 0

types of nodes
root - top of the tree
leaf - node with no children
internal nodes - node that has children

root node can be internal if there are children, but if there are no children then the root is a leaf.

Arry-ness of a tree
n-ary tree is any tree where every node in the tree has n or fewer children.

    *
         / | \     ← 3-arry tree (has three children)
        * *  *

2-arry tree - aka binary tree
each node has two or fewer children
1st pointer is known as left
second pointer is known as right