Chapter_12_Binary_Search_Trees/exercises_12.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12.2 Querying a binary search tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.2-1\n",
    "\n",
    "> Suppose that we have numbers between 1 and 1000 in a binary search tree, and we want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined?\n",
    "\n",
    "> __*a*__. 2, 252, 401, 398, 330, 344, 397, 363.\n",
    "\n",
    "> __*b*__. 924, 220, 911, 244, 898, 258, 362, 363.\n",
    "\n",
    "> __*c*__. 925, 202, 911, 240, 912, 245, 363.\n",
    "\n",
    "> __*d*__. 2, 399, 387, 219, 266, 382, 381, 278, 363.\n",
    "\n",
    "> __*e*__. 935, 278, 347, 621, 299, 392, 358, 363."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* __*c*__ is impossible since 911 < 912.\n",
    "* __*e*__ is impossible since 299 < 347."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.2-2\n",
    "\n",
    "> Write recursive versions of TREE-MINIMUM and TREE-MAXIMUM."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "def tree_minimum(root):\n",
    "    if root is None:\n",
    "        return None\n",
    "    if root.left is None:\n",
    "        return root.val\n",
    "    return tree_minimum(root.left)\n",
    "\n",
    "\n",
    "def tree_maximum(root):\n",
    "    if root is None:\n",
    "        return None\n",
    "    if root.right is None:\n",
    "        return root.val\n",
    "    return tree_maximum(root.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.2-3\n",
    "\n",
    "> Write the TREE-PREDECESSOR procedure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.parent = None\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        if left is not None:\n",
    "            left.parent = self\n",
    "        if right is not None:\n",
    "            right.parent = self\n",
    "\n",
    "\n",
    "def tree_maximum(root):\n",
    "    if root is None:\n",
    "        return None\n",
    "    if root.right is None:\n",
    "        return root\n",
    "    return tree_maximum(root.right)\n",
    "\n",
    "\n",
    "def tree_predecessor(root):\n",
    "    if root is None:\n",
    "        return None\n",
    "    if root.left is not None:\n",
    "        return tree_maximum(root.left)\n",
    "    p = root.parent\n",
    "    while p is not None and root == p.left:\n",
    "        root = p\n",
    "        p = p.parent\n",
    "    return p"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.2-4\n",
    "\n",
    "> Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key $k$ in a binary search tree ends up in a leaf. Consider three sets: $A$, the keys to the left of the search path; $B$, the keys on the search path; and $C$, the keys to the right of the search path. Professor Bunyan claims that any three keys $a \\in A$, $b \\in B$, and $c \\in C$ must satisfy $a \\le b \\le c$. Give a smallest possible counterexample to the professor's claim."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](img/12.2-4.png)\n",
    "\n",
    "3 < 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.2-5\n",
    "\n",
    "> Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If its successor has left child, then the left child is less than successor and it's larger than the node, thus the successor is not the successor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.2-6\n",
    "\n",
    "> Consider a binary search tree $T$ whose keys are distinct. Show that if the right subtree of a node $x$ in $T$ is empty and $x$ has a successor $y$, then $y$ is the lowest ancestor of $x$ whose left child is also an ancestor of $x$. (Recall that every node is its own ancestor.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TREE-SUCCESSOR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.2-7\n",
    "\n",
    "> An alternative method of performing an inorder tree walk of an $n$-node binary search tree finds the minimum element in the tree by calling TREE-MINIMUM and then making $n - 1$ calls to TREE-SUCCESSOR. Prove that this algorithm runs in $\\Theta(n)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on 12.2-8, it takes $ O(h + n + n - 1)$ time, therefore it's $\\Theta(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.2-8\n",
    "\n",
    "> Prove that no matter what node we start at in a height-$h$ binary search tree, $k$ successive calls to TREE-SUCCESSOR take $O(k + h)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $x$ is the starting node and $y$ is the ending node. The distance between $x$ and $y$ is at most $2h$, and all the edges connecting the $k$ nodes are visited twice, therefore it takes $O(k + h)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.2-9\n",
    "\n",
    "> Let $T$ be a binary search tree whose keys are distinct, let $x$ be a leaf node, and let $y$ be its parent. Show that $y.key$ is either the smallest key in $T$ larger than $x.key$ or the largest key in $T$ smaller than $x.key$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TREE-SUCCESSOR"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}