Chapter_12_Binary_Search_Trees/exercises_12.1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12.1 What is a binary search tree?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.1-1\n",
    "\n",
    "> For the set of $\\langle 1, 4, 5, 10, 16, 17, 21 \\rangle$ of keys, draw binary search trees of heights $2$, $3$, $4$, $5$, and $6$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](img/12.1-1_1.png)\n",
    "\n",
    "![](img/12.1-1_2.png)\n",
    "\n",
    "![](img/12.1-1_3.png)\n",
    "\n",
    "![](img/12.1-1_4.png)\n",
    "\n",
    "![](img/12.1-1_5.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.1-2\n",
    "\n",
    "> What is the difference between the binary-search-tree property and the min-heap property (see page 153)? Can the min-heap property be used to print out the keys of an $n$-node tree in sorted order in $O(n)$ time? Show how, or explain why not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No, heap needs $O(n \\lg n)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.1-3\n",
    "\n",
    "> Give a nonrecursive algorithm that performs an inorder tree walk."
   ]
  },
  {
   "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 inorder_tree_walk(root):\n",
    "    stack = []\n",
    "    while len(stack) > 0 or root is not None:\n",
    "        if root is None:\n",
    "            root = stack[-1]\n",
    "            del stack[-1]\n",
    "            print(root.val)\n",
    "            root = root.right\n",
    "        else:\n",
    "            stack.append(root)\n",
    "            root = root.left"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.1-4\n",
    "\n",
    "> Give recursive algorithms that perform preorder and postorder tree walks in $\\Theta(n)$ time on a tree of $n$ nodes."
   ]
  },
  {
   "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.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "def preorder_tree_walk(root):\n",
    "    if root is not None:\n",
    "        print(root.val)\n",
    "        preorder_tree_walk(root.left)\n",
    "        preorder_tree_walk(root.right)\n",
    "\n",
    "\n",
    "def postorder_tree_walk(root):\n",
    "    if root is not None:\n",
    "        postorder_tree_walk(root.left)\n",
    "        postorder_tree_walk(root.right)\n",
    "        print(root.val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.1-5\n",
    "\n",
    "> Argue that since sorting $n$ elements takes $\\Omega(n \\lg n)$ time in the worst case in the comparison model, any comparison-based algorithm for constructing a binary search tree from an arbitrary list of $n$ elements takes $\\Omega(n \\lg n)$ time in the worst case."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we construct the binary search tree by comparison-based algorithm using less than $\\Omega(n \\lg n)$ time, since the inorder tree walk is $\\Theta(n)$, then we can get the sorted elements in less than $\\Omega(n \\lg n)$ time, which contradicts the fact that sorting $n$ elements takes $\\Omega(n \\lg n)$ time in the worst case."
   ]
  }
 ],
 "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
}