%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Rooted Trees}
\label{lecture:rotted-trees}


\subsection{Class Notes}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsubsection{Definition}
\medskip

\begin{definition}\index{tree!rooted}
A \textbf{rooted tree} $T = (V,E)$ is a graph with a distinguished vertex called the \textbf{root} with the added property that every vertex $v \in V$ has an associated \textbf{level} satisfying
\begin{itemize}
\item[(1)] The level of every vertex is a nonnegative integer.
\item[(2)] The root is the unique vertex of level 0.
\item[(3)] For every edge $\{ i, j \}$ the levels of $i$ and $j$ differ by exactly 1.
\item[(4)] For every non-root vertex is adjacent to exactly one vertex of the previous level.
\end{itemize}
\end{definition}

\begin{center}
\includegraphics[height=6cm]{images/9-Rooted-Trees-tree_levels.png}
\end{center}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Terminology}
\medskip

\begin{itemize}\index{tree!rooted!height}\index{tree!rooted!parent}\index{tree!rooted!child}\index{tree!rooted!internal}\index{tree!rooted!external}\index{tree!rooted!ancestor}\index{tree!rooted!descendant}

\item[$\bullet$] The \textbf{height} of a rooted tree is the maximum level of a vertex.  A rooted tree consisting of just a root vertex has height 0. 

\item[$\bullet$] By definition, every non-root vertex $v$ with level $i$ is adjacent to exactly one vertex $u$ with level $i-1$.  We call $u$ \emph{the} \textbf{parent} of $v$ and we say that $v$ is \emph{a} \textbf{child} of $u$.  

\item[$\bullet$] A vertex of a rooted tree is \textbf{internal} if it has a child and otherwise we call it \textbf{external}.  Note that the root is always internal unless the tree has just one vertex.  

\item[$\bullet$] For every vertex $v$ there is a walk ``up the tree'' to the root obtained by moving to the parent vertex at each step.  If $u$ is another vertex on this walk, we call $u$ an \textbf{ancestor} of $v$ and $v$ a \textbf{descendant} of $u$.  Note: the root is an ancestor of every other vertex.
\end{itemize}

\begin{center}
\includegraphics[height=6cm]{images/9-Rooted-Trees-tree_levels.png}
\end{center}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Subtrees}
\medskip

We are frequently interested in working with rooted trees in a recursive manner.  Therefore, it will be helpful to think of a rooted tree as composed out of smaller rooted trees.  Here we provide a basic definition to facilitate this.  

Observation:
Let $v$ be a vertex of a rooted tree $T$ with level $i$.  Define $T'$ to be the subgraph of $T$ induced by $v$ together with its descendants.  Then $T'$ forms a new rooted tree with root vertex $v$.  (The level of a vertex in $T'$ will be $i$ smaller than its level in $T$).  We say that $T'$ with root $v$ is the \textbf{subtree} of $T$ at $v$. \index{tree!subtree}


\begin{example}

~

\includegraphics[height=6cm]{images/9-Rooted-Trees-rooted-tree-example.png}
\vspace{1cm}
\end{example}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Isomorphism}

\begin{definition}\index{tree!isomorphism of rooted trees}
Let $T_1, T_2$ be rooted trees with $T_i = (V_i, E_i)$ for $i=1,2$.  We say that $T_1$ and $T_2$ are \textbf{isomorphic} if there exists a bijection $f : V_1 \rightarrow V_2$ satisfying:
\begin{itemize}
\item[$(1)$]  $\{ f(u), f(v) \} \in E_2 \Leftrightarrow  \{u,v\} \in E_1 $
\item[$(2)$]  For every $v \in V_1$ the level of $v$ and $f(v)$ is the same.  In particular, $f$ sends the root of $T_1$ to the root of $T_2$.
\end{itemize}
\end{definition}

\begin{example}

~
\vspace{5cm}


\end{example}


\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Listing rooted trees}

Note: we will always work with rooted trees up to isomorphism.  

\begin{definition}\index{tree!binary}
A rooted tree is $m$-\textbf{ary} if every internal node has at most $m$ children.  A 2-ary tree is also called \textbf{binary}.  
\end{definition}

\begin{exercise} 
Find all binary trees with height 0, 1, and 2.
 
\vspace{6cm}
\end{exercise}







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Counting rooted trees}

We can use the recursive structure of rooted trees to count them by way of recurrences.  


\begin{exercise} 
Let $b_n$ denote the number of binary trees of height at most $n$.  From the previous slide we know
\[ b_0 = 1 \qquad b_1 = 3 \qquad b_2 = 10. \]
Find a recurrence for $b_n$.

\vspace{8cm}

\end{exercise}


\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Ordering the children}

For some applications it is essential to have not just a rooted tree, but also an ordering of the children for each internal vertex.  

\begin{example}
We can describe an arithmetic expression using a rooted tree, but we need to keep track of the order of the children.

\[  (3 + 10) - ( (3 * (5 - 1) ) / (2 * 3) ) \]

\vspace{5cm}
\end{example}






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Ordered rooted trees}
\medskip

\begin{definition}\index{tree!ordered rooted}
An \textbf{ordered} rooted tree consists of a rooted tree $T$ together with some linear orders.  Namely, for each internal vertex $v$ of $T$ the children of $v$ are arranged from first to last.  
\end{definition}

\noindent
When drawing an ordered tree, we arrange the children of $v$ from left to right according to the given order.  

\begin{example}

~
\vspace{3cm}
\end{example}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Isomorphism}

\begin{definition}\index{tree!isomorphism of ordered rooted trees}
Two ordered rooted trees are \textbf{isomorphic} if there is an isomorphism between them preserving the linear orders.  This means that two ordered rooted trees are only isomorphic if their drawings look the same (without moving any vertices).  
\end{definition}

\begin{example}

~
\vspace{2cm}
\end{example}


\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Counting ordered rooted trees}

Just as we did with rooted trees, we can establish recurrence relations for families of ordered rooted trees.

\medskip

\begin{exercise} Let $c_n$ be the number of ordered binary trees of height at most $n$.  Determine $c_0, c_1, c_2$ by explicitly listing these trees.  Then find a recurrence relation for $c_n$.

\vspace{16cm}
\end{exercise}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Additional Comments: Rooted Trees
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Additional Comments}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Exercises: Rooted Trees
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip
\bigskip
\bigskip

\hrule
\subsection{Exercises}


\renewcommand{\theenumi}{\arabic{enumi}}  %back to numbered labels
\renewcommand{\labelenumi}{\theenumi.}
\begin{enumerate}

\item

\end{enumerate}
