Goal: More Binary Trees
Balanced Tree Definition: All subtrees heights differ by no more than 1, and all subtrees are balanced.IMAGE
Various components that will be in our garbage binary tree: (don't write any of these)
//what goes here?
-getData() (maybe) setData... but making a new node to replace it works too.
//If the tree is tally based rather than storing duplicates:
add(T data) //wrapper that calls the recursive add function
add(TreeNode<T>,T data) // if there is space: add it
// otherwise, move on to the next child}
if (null) → new root
if (root does not have two children) → add to the null spot
else → add to one of the subtrees using recursive add(root,value)
how to pick which child?
-the shorter height
The height of the tree is log n. Ideally, the add function is O(log n) and the worst case scenario is O(n).
How do we print these trees?
Tree Transversals - O(n)
VCLCR= 5 6 8 9 7 1 2 (Pre-Order)
CLCRV= 8 9 6 1 2 7 5 (Post-Order)
CLVCR= 8 6 9 5 1 7 2 (In-Order)
V=Value CL=Left Child CR=Right Child