# Self Balancing Binary Tree - Question 4 Answers

## 4

\begin{algorithm}
\caption{Binary Search Tree Rotations}
\begin{algorithmic}
\REQUIRE $\text{rotate_node}$ = binary tree node
\FUNCTION{rotateRight}{$\text{rotate_node}$}
\STATE $\text{swap_node}$ $\gets$ $\text{rotate_node}$.left
\STATE $\text{rotate_node}$.left $\gets$ $\text{swap_node}$.right
\STATE
\IF{$\text{swap_node}$.right $\neq$ NULL}
\STATE $\text{swap_node}$.right.parent $\gets$ $\text{rotate_node}$
\ENDIF
\STATE
\STATE $\text{swap_node}$.parent $\gets$ $\text{rotate_node}$.parent
\STATE
\IF{$\text{rotate_node}$.parent = NULL}
\STATE root $\gets$ $\text{swap_node}$ \COMMENT{tree root becomes $\text{swap_node}$}
\ELSEIF{$\text{rotate_node}$ = $\text{rotate_node}$.parent.right}
\STATE $\text{rotate_node}$.parent.right = $\text{swap_node}$
\ELSE
\STATE $\text{rotate_node}$.parent.left = $\text{swap_node}$;
\ENDIF
\STATE
\STATE $\text{swap_node}$.right $\gets$ $\text{rotate_node}$
\STATE $\text{rotate_node}$.parent $\gets$ $\text{swap_node}$
\ENDFUNCTION
\STATE
\REQUIRE $\text{rotate_node}$ = binary tree node
\FUNCTION{rotateLeft}{$\text{rotate_node}$}
\STATE $\text{swap_node}$ $\gets$ $\text{rotate_node}$.right
\STATE $\text{rotate_node}$.right $\gets$ $\text{swap_node}$.left
\STATE
\IF{$\text{swap_node}$.left $\neq$ NULL}
\STATE $\text{swap_node}$.left.parent $\gets$ $\text{rotate_node}$
\ENDIF
\STATE
\STATE $\text{swap_node}$.parent $\gets$ $\text{rotate_node}$.parent
\STATE
\IF{$\text{rotate_node}$.parent = NULL}
\STATE root $\gets$ $\text{swap_node}$ \COMMENT{tree root becomes $\text{swap_node}$}
\ELSEIF{$\text{rotate_node}$ = $\text{rotate_node}$.parent.left}
\STATE $\text{rotate_node}$.parent.left = $\text{swap_node}$
\ELSE
\STATE $\text{rotate_node}$.parent.right = $\text{swap_node}$;
\ENDIF
\STATE
\STATE $\text{swap_node}$.left $\gets$ $\text{rotate_node}$
\STATE $\text{rotate_node}$.parent $\gets$ $\text{swap_node}$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}


The pseudo code above is notoriously confusing upon first encounter. In order to aid understating, the image below illustrates a right rotation with pseudo code line number annotations.