\documentclass[12pt]{article}

\usepackage{fullpage,amsmath,amsfonts,hyperref}

\begin{document}

\title{Algorithms and Data Structures}
\author{Summer Semester 2025}
\date{For discussion on Wednesday, June 4, 2025}
\maketitle

\begin{enumerate}


\item Provide a proof of GTG, Proposition 8.4: The height of a
nonempty tree $T$ is equal to the maximum of the depths of its leaf
positions.

\item Write a self-contained implementation of a linked binary tree
class in Python.  You may do this without using abstract base classes
or an abstract position class.  You should implement the following
methods: \verb+T.root()+, \verb+T.parent(v)+, \verb+T.left(v)+ (return
left child), \verb+T.right(v)+ (return right child), \verb+len+,
\verb+T.is_empty()+, \verb+T.is_leaf(v)+, \verb+T.add_root(e)+,
\verb+T.add_left(v,e)+ (error if there is already a left child at node
$v$, otherwise, if $e$ is a tree, attach it as the left subtree to $v$
and reset it to an empty tree, if $e$ is any other Python object,
create a new leaf node as the left child of $v$ with element $e$),
\verb+T.add_right(v,e)+ (likewise for right child),
\verb+T.replace(v,e)+, \verb+T.delete(v)+ (error if $v$ has two
children, otherwise remove $v$ from the tree, attaching its child, if
there is one, to its parent and returning the element stored in $v$).

\item (GTG Exercise R-8.5) Describe an algorithm, relying only on
binary tree operations, that counts the number of leaves in a binary
tree that are the left child of their respective parent.


\item (GTG Exercise R-8.20) Draw a binary tree $T$ that simultaneously
satisfies the following:
\begin{itemize}
\item Each internal node of $T$ stores a single character.
\item A preorder traversal of $T$ yields EXAMFUN.
\item An inorder traversal of $T$ yields MAFXUEN.
\end{itemize}

\item (GTG Exercise of R-8.23) Let $T$ be an ordered tree with more
than one node. Is it possible that the preorder traversal of $T$
visits the nodes in the same order as the postorder traversal of $T$?
If so, give an example; otherwise, explain why this cannot
occur. Likewise, is it possible that the preorder traversal of $T$
visits the nodes in the reverse order of the postorder traversal of
$T$? If so, give an example; otherwise, explain why this cannot occur.



\end{enumerate}
\end{document}
