I think that I shall never see code as lovely as a tree - 401-advanced-javascript-aimurphy/seattle-javascript-401n13 GitHub Wiki

Tree Anatomy

I think that I shall never see A poem lovely as a tree. A tree whose hungry mouth is prest Against the earth's sweet flowing breast; A tree that looks at God all day, And lifts her leafy arms to pray; A tree that may in summer wear A nest of robins in her hair; Upon whose bosom snow has lain; Who intimately lives with rain. Poems are made by fools like me, But only God can make a tree.

-Joyce Kilmer

  • Root - the top node, the tree's beginning

  • Left and Right child - the split from the root, left and right

  • Edge - (I need to ask on this) a link between 2 nodes, the branch

  • Leaf - a node w/out kids, the terminus of the tree--root to leaf

  • Height - how many branches deep a tree is from the root to the highest leaf

How to climb a tree... like a programmer

A. Depth First

This means climbing the height of the tree. We can go about this at least three ways: start at the root and climb each side root to leaf; start on one side, back to the root, and hit the other; or start at the leaves and work in to the root. In other words:

  1. Preorder Root, Left, Right

  2. Inorder Left, Root, Right

  3. Postorder Left, Right, Root

WAT?

Picture: cf tree

PRE: a-b-d-e-c-f i care about it as soon as i see it(11:20)

IN: d-b-e-a-f-c go down the the bottom and look backwards... I care about the node BETWEEN @1143

POST: d-e-b-f-c-a i care about the end, so start at the end and look back

big(o) is o(h) we care about the height of the tree.

at the worst we will be at the bottom of the tree

If that wasn't clear, here is a

2. Breadth First

you approach by seeing all the nodes, and you'll use queuue(@ 1113) enqueues the kids of each node.

we deal with the width of the tree at each tier of the height

Space processing is o(w) width of the tree time processing is o(n) number of things (nodes)

john's talk!

stacks and queues and ll are used for OREDER INFO . these are for predicatble marches through a process they have some info like front back top bottom etc...

but the TREES! the trees are for the hierarchical organziation

it's a family tree!! You can look up K-ary trees on your own. intstead of R/L kids they have and array of kids because they have hecka nodes kids. Think HTML and the DOM. 😉

*sample final question: given a binary tree, give the highest value assigned to a a leaf

file system is a TREE!!

balanced tree is <= 1 difference in height

if you are 2+ height different on your left or right your tree is out of balance! see @ 10:58am

did you know linked lists are trees too? Super unbalanced trees, they only have a next (which could be likened to the .left or .right of the tree!)

tree props: .root .left .right .leaf

BST (not mad cow) Rules: left is less, right is greater @11:04

ex: if you have the number 10, and then you get 12, 12 is going to the right 4? itll go to the right of 10

then 11? bigger than 10, itll branch off of 12, but to the left since it is smaller

9? less than 10, to the right (brnaching off four) but will be right child of 4 becauses bigger than 4.

so if you have an ordered array, you begin your tree from the middle point in order to set yourself up for balance (@1106)... and the binary search tree cuts your search time in half! the values added in will be sorted upon instertions.

you are taking in each level, and taking in the kids of each parent as you go along, making your next level

TRIE Tree @ 11:09 d-o d-o-g