\documentclass[10pt,a4paper]{article}

% Packages
\usepackage{fancyhdr}           % For header and footer
\usepackage{multicol}           % Allows multicols in tables
\usepackage{tabularx}           % Intelligent column widths
\usepackage{tabulary}           % Used in header and footer
\usepackage{hhline}             % Border under tables
\usepackage{graphicx}           % For images
\usepackage{xcolor}             % For hex colours
%\usepackage[utf8x]{inputenc}    % For unicode character support
\usepackage[T1]{fontenc}        % Without this we get weird character replacements
\usepackage{colortbl}           % For coloured tables
\usepackage{setspace}           % For line height
\usepackage{lastpage}           % Needed for total page number
\usepackage{seqsplit}           % Splits long words.
%\usepackage{opensans}          % Can't make this work so far. Shame. Would be lovely.
\usepackage[normalem]{ulem}     % For underlining links
% Most of the following are not required for the majority
% of cheat sheets but are needed for some symbol support.
\usepackage{amsmath}            % Symbols
\usepackage{MnSymbol}           % Symbols
\usepackage{wasysym}            % Symbols
%\usepackage[english,german,french,spanish,italian]{babel}              % Languages

% Document Info
\author{BearTeddy}
\pdfinfo{
  /Title (binary-search-tree-c.pdf)
  /Creator (Cheatography)
  /Author (BearTeddy)
  /Subject (Binary Search Tree C++ Cheat Sheet)
}

% Lengths and widths
\addtolength{\textwidth}{6cm}
\addtolength{\textheight}{-1cm}
\addtolength{\hoffset}{-3cm}
\addtolength{\voffset}{-2cm}
\setlength{\tabcolsep}{0.2cm} % Space between columns
\setlength{\headsep}{-12pt} % Reduce space between header and content
\setlength{\headheight}{85pt} % If less, LaTeX automatically increases it
\renewcommand{\footrulewidth}{0pt} % Remove footer line
\renewcommand{\headrulewidth}{0pt} % Remove header line
\renewcommand{\seqinsert}{\ifmmode\allowbreak\else\-\fi} % Hyphens in seqsplit
% This two commands together give roughly
% the right line height in the tables
\renewcommand{\arraystretch}{1.3}
\onehalfspacing

% Commands
\newcommand{\SetRowColor}[1]{\noalign{\gdef\RowColorName{#1}}\rowcolor{\RowColorName}} % Shortcut for row colour
\newcommand{\mymulticolumn}[3]{\multicolumn{#1}{>{\columncolor{\RowColorName}}#2}{#3}} % For coloured multi-cols
\newcolumntype{x}[1]{>{\raggedright}p{#1}} % New column types for ragged-right paragraph columns
\newcommand{\tn}{\tabularnewline} % Required as custom column type in use

% Font and Colours
\definecolor{HeadBackground}{HTML}{333333}
\definecolor{FootBackground}{HTML}{666666}
\definecolor{TextColor}{HTML}{333333}
\definecolor{DarkBackground}{HTML}{6C91A3}
\definecolor{LightBackground}{HTML}{F5F8F9}
\renewcommand{\familydefault}{\sfdefault}
\color{TextColor}

% Header and Footer
\pagestyle{fancy}
\fancyhead{} % Set header to blank
\fancyfoot{} % Set footer to blank
\fancyhead[L]{
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{C}
    \SetRowColor{DarkBackground}
    \vspace{-7pt}
    {\parbox{\dimexpr\textwidth-2\fboxsep\relax}{\noindent
        \hspace*{-6pt}\includegraphics[width=5.8cm]{/web/www.cheatography.com/public/images/cheatography_logo.pdf}}
    }
\end{tabulary}
\columnbreak
\begin{tabulary}{11cm}{L}
    \vspace{-2pt}\large{\bf{\textcolor{DarkBackground}{\textrm{Binary Search Tree C++ Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{BearTeddy} via \textcolor{DarkBackground}{\uline{cheatography.com/84248/cs/19903/}}}
\end{tabulary}
\end{multicols}}

\fancyfoot[L]{ \footnotesize
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{LL}
  \SetRowColor{FootBackground}
  \mymulticolumn{2}{p{5.377cm}}{\bf\textcolor{white}{Cheatographer}}  \\
  \vspace{-2pt}BearTeddy \\
  \uline{cheatography.com/bearteddy} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Published 21st June, 2019.\\
   Updated 21st June, 2019.\\
   Page {\thepage} of \pageref{LastPage}.
\end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Sponsor}}  \\
  \SetRowColor{white}
  \vspace{-5pt}
  %\includegraphics[width=48px,height=48px]{dave.jpeg}
  Measure your website readability!\\
  www.readability-score.com
\end{tabulary}
\end{multicols}}




\begin{document}
\raggedright
\raggedcolumns

% Set font size to small. Switch to any value
% from this page to resize cheat sheet text:
% www.emerson.emory.edu/services/latex/latex_169.html
\footnotesize % Small font.

\begin{multicols*}{3}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{BST AVL Struct}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{template \textless{}class T\textgreater{} \newline class TreeNode \{ \newline private: \newline     T \_item; \newline     TreeNode\textless{}T\textgreater{}{\emph{ \_left; \newline     TreeNode\textless{}T\textgreater{}}} \_right; \newline     //Could include \newline     TreeNode\textless{}T\textgreater{}* \_parent; \newline     int \_height; \newline public: \newline     TreeNode(T x) \{ \newline      \_left = \_right = NULL; \newline      \_item = x;  \newline      \_height = 0;  \}; \newline      friend BinarySearchTree\textless{}T\textgreater{}; \newline \};} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{\_item = value \newline \_height = height of the node ( will have to calculate ) \newline \_left , \_right = default set to NULL in public constructor.}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Search Max,Min}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{template \textless{}class T\textgreater{} \newline T BinarySearchTree\textless{}T\textgreater{}::searchMax() \{ \newline      TreeNode\textless{}T\textgreater{}{\emph{ current = \_root; \newline      while (current-\textgreater{}\_right) \{ \newline            current = current-\textgreater{}\_right; \newline       \} \newline       return current-\textgreater{}\_item; \newline \} \newline  \newline template \textless{}class T\textgreater{} \newline T BinarySearchTree\textless{}T\textgreater{}::searchMin() \{ \newline       TreeNode\textless{}T\textgreater{}}} current = \_root; \newline       while (current-\textgreater{}\_left) \{ \newline       current = current-\textgreater{}\_left; \newline       \} \newline       return current-\textgreater{}\_item; \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Successor}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{template \textless{}class T\textgreater{} \newline T BinarySearchTree\textless{}T\textgreater{}::successor(T x)\{ \newline      TreeNode\textless{}T\textgreater{}* root = \_root; \newline      T succ = NULL; \newline      while (root != NULL) \{ \newline        if (x \textless{} root-\textgreater{}\_item)\{ \newline            succ = root-\textgreater{}\_item; \newline            root = root-\textgreater{}\_left; \newline         \} \newline         else\{ \newline            root = root-\textgreater{}\_right; \newline         \} \newline     \} \newline     return succ; \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{exist() // iterative}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{//Iterative \newline template \textless{}class T\textgreater{} \newline bool BinarySearchTree\textless{}T\textgreater{}::exist(T x) \{ \newline         TreeNode\textless{}T\textgreater{}* nd = \_root; \newline         while (nd != NULL) \{ \newline                 if (nd-\textgreater{}\_item == x) return true; \newline                 if (nd-\textgreater{}\_item \textgreater{} x) nd = nd-\textgreater{}\_left; \newline                 else  nd = nd-\textgreater{}\_right; \newline         \} \newline         return false; \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{exit() // Recursive}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{template \textless{}class T\textgreater{} \newline bool BinarySearchTree\textless{}T\textgreater{}::exist(TreeNode\textless{}T\textgreater{} Node,T x) \{ \newline          // RECURSIVE  \newline          exists ( \_root , value x ) \newline          if (\_root == null) return false; \newline          if (\_root-\textgreater{}\_item == x) return true; \newline          if (\_root-\textgreater{}\_item \textgreater{} x)  \newline             return exists ( \_root-\textgreater{}left, x); \newline          else  exists ( \_root-\textgreater{}right, x ); \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{LR RL Rotation}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{//LR Rotation \newline template \textless{}class T\textgreater{} \newline TreeNode\textless{}T\textgreater{}{\emph{ BinarySearchTree\textless{}T\textgreater{}::\_leftrightRotation(TreeNode\textless{}T\textgreater{}}} node) \newline \{ \newline 	node-\textgreater{}\_left = \_rightRotation(node-\textgreater{}\_left); \newline 	node = \_leftRotation(node); \newline 	return node; \newline \} \newline  \newline //RL Rotation \newline template \textless{}class T\textgreater{} \newline TreeNode\textless{}T\textgreater{}{\emph{ BinarySearchTree\textless{}T\textgreater{}::\_rightleftRotation(TreeNode\textless{}T\textgreater{}}} node) \{ \newline 	node-\textgreater{}\_right = \_leftRotation(node-\textgreater{}\_right); \newline 	node = \_rightRotation(node); \newline 	return node; \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{PreOrderPrint}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{template \textless{}class T\textgreater{} \newline void BinarySearchTree\textless{}T\textgreater{}::\_preOrderPrint(TreeNode\textless{}T\textgreater{}* node) \{ \newline       if (!node) return; \newline       cout \textless{}\textless{} node-\textgreater{}\_item \textless{}\textless{} " "; \newline       \_preOrderPrint(node-\textgreater{}\_left); \newline       \_preOrderPrint(node-\textgreater{}\_right); \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{InOrderPrint}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{template \textless{}class T\textgreater{} \newline void BinarySearchTree\textless{}T\textgreater{} :: \_inOrderPrint(TreeNode\textless{}T\textgreater{}* node) \{ \newline       if (!node) return; \newline       \_inOrderPrint(node-\textgreater{}\_left); \newline       cout \textless{}\textless{} node-\textgreater{}\_item \textless{}\textless{} " "; \newline       \_inOrderPrint(node-\textgreater{}\_right); \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{PostOrderPrint}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{template \textless{}class T\textgreater{} \newline void BinarySearchTree\textless{}T\textgreater{}:: \_postOrderPrint(TreeNode\textless{}T\textgreater{}* node) \{ \newline      if (!node) return; \newline      \_postOrderPrint(node-\textgreater{}\_left); \newline      \_postOrderPrint(node-\textgreater{}\_right); \newline      cout \textless{}\textless{} node-\textgreater{}\_item \textless{}\textless{} " "; \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Height}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{template \textless{}class T\textgreater{} \newline int BinarySearchTree\textless{}T\textgreater{}::height(TreeNode\textless{}T\textgreater{}{\emph{ node) \{ \newline 	return node == NULL ? -1 : (node-\textgreater{}\_height); \newline \} \newline  \newline template \textless{}class T\textgreater{} \newline int BinarySearchTree\textless{}T\textgreater{}::\_calheight(TreeNode\textless{}T\textgreater{}}} node) \{ \newline    int leftHeight = -1; \newline    int rightHeight = -1; \newline    if (node != NULL) \{ \newline      if (node-\textgreater{}\_left != NULL) \{  \newline         leftHeight = \_calheight(node-\textgreater{}\_left); \newline      \} \newline      if (node-\textgreater{}\_right != NULL) \{ \newline       rightHeight = \_calheight(node-\textgreater{}\_right); \newline      \} \newline    \} \newline    return max(leftHeight, rightHeight) + 1; \newline \} \newline  \newline //Height from TA \newline template \textless{}class T\textgreater{} \newline void TreeNode\textless{}T\textgreater{}::rectifyHeight() \newline \{ \newline  int left = \_left ? \_left-\textgreater{}\_height : -1; \newline  int right = \_right ? \_right-\textgreater{}\_height : -1; \newline //Height Value \newline  \_height = (left \textgreater{} right ? left : right) + 1; \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Insert}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{//Task 1 and 6 \newline template \textless{}class T\textgreater{} \newline TreeNode\textless{}T\textgreater{}{\emph{ BinarySearchTree\textless{}T\textgreater{}::\_insert(TreeNode\textless{}T\textgreater{}}} current, T x) \{ \newline     if (current-\textgreater{}\_item \textgreater{} x) \{ \newline       if (current-\textgreater{}\_left) \newline         current-\textgreater{}\_left = \_insert(current-\textgreater{}\_left, x); \newline       else \{ \newline         current-\textgreater{}\_left = new TreeNode\textless{}T\textgreater{}(x); \newline         \_size++; \newline        \} \newline      \} \newline     else if (x \textgreater{} current-\textgreater{}\_item) \{ \newline       if (current-\textgreater{}\_right) \newline          current-\textgreater{}\_right = \_insert(current-\textgreater{}\_right, x); \newline       else\{ \newline          current-\textgreater{}\_right = new TreeNode\textless{}T\textgreater{}(x); \newline          \_size++; \newline        \} \newline      \} \newline      else \newline //item already exists, dont need do anything \newline       return current;} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Code From TA// Rotation}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{//-1 if no children, st bf will work  \newline int left = current-\textgreater{}\_left ? current-\textgreater{}\_left-\textgreater{}\_height : -1; \newline  \newline int right = current-\textgreater{}\_right ? current-\textgreater{}\_right-\textgreater{}\_height : -1; \newline  \newline current-\textgreater{}\_height = (left \textgreater{} right ? left : right) + 1; \newline      \newline   //GET DIFF IN height \newline   if (abs(left - right) \textgreater{} 1)\{ \newline       \newline if (left \textgreater{} right)\{ \newline  \newline        int LLH = current-\textgreater{}\_left-\textgreater{}\_left ? current-\textgreater{}\_left-\textgreater{}\_left-\textgreater{}\_height : 0; \newline         \newline        int LRH = current-\textgreater{}\_left-\textgreater{}\_right ? current-\textgreater{}\_left-\textgreater{}\_right-\textgreater{}\_height : 0; \newline  \newline     if (LLH \textless{} LRH)\{ \newline     current-\textgreater{}\_left = \_leftRotation(current-\textgreater{}\_left); \newline     \} \newline     current = \seqsplit{\_rightRotation(current);} \newline  \newline \} \newline else \{ \newline     int RLH = current-\textgreater{}\_right-\textgreater{}\_left ? current-\textgreater{}\_right-\textgreater{}\_left-\textgreater{}\_height : 0; \newline  \newline     int RRH = current-\textgreater{}\_right-\textgreater{}\_right ? current-\textgreater{}\_right-\textgreater{}\_right-\textgreater{}\_height : 0; \newline  \newline     if (RRH \textless{} RLH)\{ \newline     current-\textgreater{}\_right = \_rightRotation(current-\textgreater{}\_right); \newline     \} \newline     current = \_leftRotation(current); \newline  \newline  \} \newline  \newline \} \newline  \newline //go through tree and rect height  \newline  \newline    current-\textgreater{}rectifyHeight(); \newline    return current; \newline  \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{LL RR Rotation}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{//LL Rotation \newline template \textless{}class T\textgreater{} \newline TreeNode\textless{}T\textgreater{}{\emph{ BinarySearchTree\textless{}T\textgreater{}::\_leftRotation(TreeNode\textless{}T\textgreater{}}} node) \newline \{ \newline 	TreeNode\textless{}T\textgreater{}{\emph{ nd; \newline 	nd = node-\textgreater{}\_left; \newline 	node-\textgreater{}\_left = nd-\textgreater{}\_right; \newline 	nd-\textgreater{}\_right = node; \newline  \newline 	nd-\textgreater{}\_height = calheight(nd); \newline 	node-\textgreater{}\_height = calheight(node); \newline 	return nd; \newline 	 \newline  \newline 	/}} \newline 	{\emph{ \newline 	}}Codes from tutorialshorizon \newline 	{\emph{copyrights to - \seqsplit{https://algorithms.tutorialhorizon.com/avl-tree-insertion/} \newline 	}} \newline 	//{\emph{/ \newline 	//TreeNode\textless{}T\textgreater{}}} nd = node-\textgreater{}\_right; \newline 	//TreeNode\textless{}T\textgreater{}{\emph{ T2 = nd-\textgreater{}\_left; \newline 	//nd-\textgreater{}\_left = node; \newline 	//node-\textgreater{}\_right = T2; \newline 	//nd-\textgreater{}\_height = calheight(nd); \newline 	//node-\textgreater{}\_height = calheight(node); \newline 	//return nd; \newline \} \newline  \newline //RR Rotation \newline template \textless{}class T\textgreater{} \newline TreeNode\textless{}T\textgreater{}}} BinarySearchTree\textless{}T\textgreater{}::\_rightRotation(TreeNode\textless{}T\textgreater{}{\emph{ node) \newline \{ \newline  \newline 	TreeNode\textless{}T\textgreater{}}} nd; \newline 	nd = node-\textgreater{}\_right; \newline 	node-\textgreater{}\_right = nd-\textgreater{}\_left; \newline 	nd-\textgreater{}\_left = node; \newline 	nd-\textgreater{}\_height = calheight(nd); \newline 	node-\textgreater{}\_height = calheight(node); \newline 	return nd; \newline  \newline 	/{\emph{ \newline 	}} \newline 	{\emph{Codes from tutorialshorizon \newline 	}}copyrights to - \seqsplit{https://algorithms.tutorialhorizon.com/avl-tree-insertion/} \newline 	{\emph{ \newline 	}} \newline 	{\emph{//}} \newline 	TreeNode\textless{}T\textgreater{}{\emph{ nd = node-\textgreater{}\_left; \newline 	TreeNode\textless{}T\textgreater{}}} T2 = nd-\textgreater{}\_right; \newline 	nd-\textgreater{}\_right = node; \newline 	node-\textgreater{}\_left = T2; \newline 	nd-\textgreater{}\_height = calheight(nd); \newline 	node-\textgreater{}\_height = calheight(node); \newline 	return nd;*/ \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


% That's all folks
\end{multicols*}

\end{document}