AVL Tree Height Edges Leaf/Leaf Node Balance Factor Left Heavy Right Heavy Balanced Node
<aside> 💡 A AVL Tree is a self balancing kind of BST that guarantees height is never worse than $O(log n)$. Recall that with standard Binary Search Trees, the runtime depends on the height of the tree which can be as bad as $O(n)$ if the tree isn’t balanced.
</aside>
<aside> 💡 The height of any node is the max of the number of edges (the connection between nodes, represented by a line) from that node to a leaf (a node that has no children).
</aside>
<aside> 💡 The Balance Factor is used to determine if a tree is left/right heavy or is balanced. The Balance Factor, $BF$ of a node, $v$ can be determined by the height of the right subtree minus the height of the left sub tree:
</aside>
$$ BF(v) = height(T_R) - height(T_L) $$
<aside>
💡 When determining the Balance Factor of a leaf node, the height of the left child and the height of the right child is NULL.When the height of any subtree is NULL, it is equal to -1.
</aside>
$$ height(T_R) = height(null) = -1 \newline neight(T_L) = height(null) = -1 $$
<aside> 💡 If the Balance Factor of a node is smaller than -1, the tree is left heavy. If the Balance Factor of a node is greater than 1, the tree is right heavy. A Balance Factor of -1, 0, or 1 denotes a balanced node.
</aside>
<aside> 💡 An AVL is a BST where all the nodes are balanced i.e $\space \forall u \isin v \space |BF(u)| \le 1$.
</aside>
<aside> 💡 Find the height and balance factor of this tree.
</aside>