Exercise 12.3-4

Is the operation of deletion “commutative” in the sense that deleting $x$ and then $y$ from a binary search tree leaves the same tree as deleting $y$ and then $x$? Argue why it is or give a counterexample.

Deletion is not always commutative. Suppose we are deleting nodes 2 and 1 in both possible orders for the following binary search tree $T$:

$12.3-4 Binary Search Tree Base$

Consider deleting nodes $1$ and $2$ in ascending order:

$12.3-4 Binary Search Tree Order 1$

Now consider deleting nodes $1$ and $2$ in the alternative order:

$12.3-4 Binary Search Tree Order 2$

The following LaTeX code was used to generate the above binary search tree $T$:

\documentclass[12pt,a4paper]{article}
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  shade/.style = {fill=black!15},
  level/.style = {sibling distance = 20mm/#1}
  ]
  \node {2}
  child {node {1}
        child {edge from parent[draw = none]}
        child {edge from parent[draw = none]}}
  child {node {4}
        child {node {3}}
        child {edge from parent[draw = none]}};
\end{tikzpicture}
\end{document}

The following LaTeX code was used to generate the above pair of binary search trees in order 2:

\documentclass[12pt,a4paper]{article}
\usepackage[labelformat=empty]{caption}
\usepackage{tikz}
\tikzset{mynode/.style={inner sep=2pt,fill,outer sep=0,circle}}
\newcommand{\mycaption}[2]{\caption[#1]{\textbar\, \textbf{#1.} #2}}
\begin{document}

\begin{center}
\begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  shade/.style = {fill=black!15},
  level/.style = {sibling distance = 20mm/#1}
  ]
  \node {2}
  child {edge from parent[draw = none]}
  child {node {4}
        child {node {3}}
        child {edge from parent[draw = none]}};
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  shade/.style = {fill=black!15},
  level/.style = {sibling distance = 20mm/#1}
  ]
  \node {4}
  child {node {3}}
  child {edge from parent[draw = none]};
\end{tikzpicture}
\end{center}
\captionof{figure}{TREE-DELETE(T, 1) then TREE-DELETE(T, 2)}
\end{document}

The following LaTeX code was used to generate the above pair of binary search trees in order 2:

\documentclass[12pt,a4paper]{article}
\usepackage[labelformat=empty]{caption}
\usepackage{tikz}
\tikzset{mynode/.style={inner sep=2pt,fill,outer sep=0,circle}}
\newcommand{\mycaption}[2]{\caption[#1]{\textbar\, \textbf{#1.} #2}}
\begin{document}

\begin{center}
\begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  shade/.style = {fill=black!15},
  level/.style = {sibling distance = 20mm/#1}
  ]
  \node {3}
  child {node {1}
        child {edge from parent[draw = none]}
        child {edge from parent[draw = none]}}
  child {node {4}
        child {edge from parent[draw = none]}
        child {edge from parent[draw = none]}};
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  shade/.style = {fill=black!15},
  level/.style = {sibling distance = 20mm/#1}
  ]
  \node {3}
  child {edge from parent[draw = none]}
  child {node {4}
        child {edge from parent[draw = none]}
        child {edge from parent[draw = none]}};
\end{tikzpicture}
\end{center}
\captionof{figure}{TREE-DELETE(T, 2) then TREE-DELETE(T, 1)}
\end{document}