array-list.ipynb

balanced-bsts-demo.ipynb

binary-search-trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Search Trees\n",
    "\n",
    "## Agenda\n",
    "\n",
    "- Binary Trees & Binary Search Trees: definitions\n",
    "- Linked tree structure and Manual construction\n",
    "- Recursive binary search tree functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Tree: def\n",
    "\n",
    "- A *binary tree* is a structure that is either empty, or consists of a *root* node containing a value and references to a left and right *sub-tree*, which are themselves binary trees.\n",
    "\n",
    "Naming nodes:\n",
    "- The single node in a binary tree without a parent is the root node of the tree\n",
    "- We say that a given node is the *parent* of its left and right *child* nodes; nodes with the same parent are called *siblings*\n",
    "- If a node has no children we call it a *leaf* node; otherwise, we call it an *internal* node\n",
    "\n",
    "Binary tree metrics (note: alternative defs are sometimes used!):\n",
    "\n",
    "- The *depth* of a node is the number of nodes from the root of the tree to that node (inclusive)\n",
    "- The *height* of a node is the number of nodes on the longest path from that node down to a leaf (inclusive)\n",
    "\n",
    "Categorizing binary trees:\n",
    "\n",
    "- A *complete* binary tree is one where all but the last level are filled, and in the last level leaves are as far to the left as possible\n",
    "- A *perfect* binary tree is one where all internal nodes have 2 children, and all leaves have the same depth\n",
    "- A *balanced* binary tree is ... ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Search Tree (BSTree): def\n",
    "\n",
    "- A *binary search tree* is a binary tree where the value contained in every node is:\n",
    "    - *greater than* all keys in its left subtree, and\n",
    "    - *less than* all keys in its right subtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked tree structure and Manual construction:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "    def __repr__(self):\n",
    "        def str_rec(t,depth):\n",
    "            if not t:\n",
    "                return \"\"\n",
    "            else:\n",
    "                return ((\"\\t\" * depth) \n",
    "                    + str(t.val) \n",
    "                    + \"\\n\" + str_rec(t.left, depth + 1) \n",
    "                    + str_rec(t.right, depth + 1))\n",
    "        \n",
    "        return str_rec(self, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursive bstree functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tmin(t):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "def max_with_none(*nums):\n",
    "    result = None\n",
    "    for n in nums:\n",
    "        if not result:\n",
    "            result = n\n",
    "        elif n: \n",
    "            result = max(result,n)\n",
    "    return result\n",
    "\n",
    "def tmax(t: Node):\n",
    "    if not t:\n",
    "        return None\n",
    "    return max_with_none(t.val, tmax(t.left), tmax(t.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find(t, x):\n",
    "    if not t:\n",
    "        return False\n",
    "    if t.val == x:\n",
    "        return True\n",
    "    if t.val > x:\n",
    "        return find(t.left, x)\n",
    "    if t.val < x:\n",
    "        return find(t.right, x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "import builtins\n",
    "max = builtins.max\n",
    "def height(t):\n",
    "    if not t:\n",
    "        return 0\n",
    "    return 1 + max([height(t.left), height(t.right)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def visit(t):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def map(t,f):\n",
    "    f(t.val)\n",
    "    if t.left:\n",
    "        map(t.left, f)\n",
    "    if t.right:\n",
    "        map(t.right, f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myt = Node(3, Node(1), Node(5))\n",
    "#print(f\"height: {height(myt)}\")\n",
    "myt\n",
    "height(myt)\n",
    "tmax(myt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "1\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "map(myt,lambda x: print (x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "find 3: True\n",
      "find 5: True\n",
      "find 1: True\n",
      "find 2: False\n"
     ]
    }
   ],
   "source": [
    "print(f\"\"\"find 3: {find(myt, 3)}\n",
    "find 5: {find(myt, 5)}\n",
    "find 1: {find(myt, 1)}\n",
    "find 2: {find(myt, 2)}\"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}

bst-ds-demo.ipynb

hashtable-demo.ipynb

iterators-demo.ipynb

lang-intro-part1.ipynb

lang-intro-part2.ipynb

lang-intro-part3.ipynb

linked-list-demo.ipynb

linked-structures-demo.ipynb

on-recursion-demo.ipynb

priority-queues-demo.ipynb

searching-sorting-timing.ipynb

stacks-and-queues-demo.ipynb