Quiz #4 Review Flashcards
For every node in PostOrder traversal:
Visit left
Visit right
print
For every node in PreOrder traversal:
Print
Visit left
Visit Right
For every node in InOrder traversal:
Visit left
Print
Visit Right
key of PostOrder traversal:
root always prints last
key of InOrder traversal:
least to greatest
key of PreOrder traversal:
root always prints first
BST benefit
they have speedy searches since all data is ordered properly around the root
BST speed
Log2(n)
Size =
of elements = n
Leaves:
Elements with no kids
Edges:
non-null links
Edges formula:
n-1
of null links formula:
n+1
of null links:
Node has no leaf
Height:
longest path from node to length
Max size formula:
2^(n+1) - 1
T/F: Not all BTs are BSTs
True
Full Tree:
at max capacity for specified height
Completed Tree:
Full to next to last level and filled in from left to right on bottom level
Balanced Tree:
balanced or not
T/F: All full trees are complete trees
True
What is the fewest amount of leaves a BST can have
1
BST:
All nodes fulfill the property of all values less than the root go to the left and all values greater then the root go to the right
Binary Tree:
each node has references to two children, however one may be null
