binary trees notes

Binary Trees

root of the tree
leaf nodes are at the bottom

invariant for binary tree-- can only have 0, 1, or 2 branches off of a thing
each thing is the value and then two pointers

BinTree[+A]
this means that the type is auto determined upon being given a value

sealed trait BinTree[+A]
keeps people from adding other types or something

two kinds-- node and empty

height of item in binary tree-- longest path from the node to a leaf
depth-- number of edges from root to node

=====

trees provide efficient insertion and searching

in order traversal -- left item right
pre order traversal -- item left right
post order traversal -- left right item
breadth first traversal -- all the items n shit

=====

def smaller(tup:(Int,Int)): (Int,Int) = tup Match {
	case (a,b) =>
		if(a<b) (a,b)
		else if(a>b) (b,a)
		else (a,a)

	case _ => (0,0)
}

=====

Binary Search Tree-- left side is less than node, right side is greater