trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f814a143",
   "metadata": {
    "papermill": {
     "duration": 0.007143,
     "end_time": "2024-08-22T10:22:26.166218",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.159075",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Binary Trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "9cd3ccb1",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-22T10:22:26.182822Z",
     "iopub.status.busy": "2024-08-22T10:22:26.182300Z",
     "iopub.status.idle": "2024-08-22T10:22:26.197466Z",
     "shell.execute_reply": "2024-08-22T10:22:26.196170Z"
    },
    "papermill": {
     "duration": 0.027621,
     "end_time": "2024-08-22T10:22:26.200727",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.173106",
     "status": "completed"
    },
    "tags": []
   },
   "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",
    "    def __str__(self):\n",
    "        return str(self.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "7c609b9f",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-22T10:22:26.215206Z",
     "iopub.status.busy": "2024-08-22T10:22:26.214747Z",
     "iopub.status.idle": "2024-08-22T10:22:26.220968Z",
     "shell.execute_reply": "2024-08-22T10:22:26.219920Z"
    },
    "papermill": {
     "duration": 0.016434,
     "end_time": "2024-08-22T10:22:26.223607",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.207173",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "a = TreeNode(1)\n",
    "b = TreeNode(2)\n",
    "c = TreeNode(3)\n",
    "d = TreeNode(4)\n",
    "e = TreeNode(5)\n",
    "\n",
    "a.left = b\n",
    "a.right = c\n",
    "b.left = d\n",
    "b.right = e"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45d707e5",
   "metadata": {
    "papermill": {
     "duration": 0.006584,
     "end_time": "2024-08-22T10:22:26.237230",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.230646",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "## Recursive Pre Order Traversal (DFS) Time: O(n), Space: O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "cf466b7d",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-22T10:22:26.253114Z",
     "iopub.status.busy": "2024-08-22T10:22:26.252623Z",
     "iopub.status.idle": "2024-08-22T10:22:26.260018Z",
     "shell.execute_reply": "2024-08-22T10:22:26.258873Z"
    },
    "papermill": {
     "duration": 0.018395,
     "end_time": "2024-08-22T10:22:26.262723",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.244328",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "4\n",
      "5\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# Pre Order: Node, Left, Right\n",
    "def pre_order(node):\n",
    "    if not node:\n",
    "        return\n",
    "    \n",
    "    print(node)\n",
    "    pre_order(node.left)\n",
    "    pre_order(node.right)\n",
    "    \n",
    "pre_order(a)    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ee76d02",
   "metadata": {
    "papermill": {
     "duration": 0.006975,
     "end_time": "2024-08-22T10:22:26.276325",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.269350",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "## Recursive In Order Traversal (DFS) Time: O(n), Space: O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "c798db5e",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-22T10:22:26.291721Z",
     "iopub.status.busy": "2024-08-22T10:22:26.291303Z",
     "iopub.status.idle": "2024-08-22T10:22:26.299640Z",
     "shell.execute_reply": "2024-08-22T10:22:26.297966Z"
    },
    "papermill": {
     "duration": 0.019094,
     "end_time": "2024-08-22T10:22:26.302364",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.283270",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "2\n",
      "5\n",
      "1\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# In Order: Left, Node, Right\n",
    "def in_order(node):\n",
    "    if not node:\n",
    "        return\n",
    "    \n",
    "    in_order(node.left)\n",
    "    print(node)\n",
    "    in_order(node.right)\n",
    "    \n",
    "in_order(a) "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ba93274",
   "metadata": {
    "papermill": {
     "duration": 0.005801,
     "end_time": "2024-08-22T10:22:26.314454",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.308653",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "## Iterative Pre Order Traversal (DFS) Time: O(n), Space: O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a34c3ac6",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-22T10:22:26.328765Z",
     "iopub.status.busy": "2024-08-22T10:22:26.328321Z",
     "iopub.status.idle": "2024-08-22T10:22:26.337223Z",
     "shell.execute_reply": "2024-08-22T10:22:26.335928Z"
    },
    "papermill": {
     "duration": 0.019419,
     "end_time": "2024-08-22T10:22:26.340036",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.320617",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "4\n",
      "5\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "def pre_order_iterative(node):\n",
    "    stk = [node]\n",
    "    \n",
    "    while stk:\n",
    "        node = stk.pop()\n",
    "        print(node)\n",
    "        \n",
    "        if node.right:\n",
    "            stk.append(node.right)\n",
    "        if node.left:\n",
    "            stk.append(node.left)\n",
    "            \n",
    "pre_order_iterative(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74b2988a",
   "metadata": {
    "papermill": {
     "duration": 0.006304,
     "end_time": "2024-08-22T10:22:26.352974",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.346670",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "## Level Order Traversal (BFS) Time: O(n), Space: O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "3bfa4ff8",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-22T10:22:26.368726Z",
     "iopub.status.busy": "2024-08-22T10:22:26.368297Z",
     "iopub.status.idle": "2024-08-22T10:22:26.376563Z",
     "shell.execute_reply": "2024-08-22T10:22:26.375115Z"
    },
    "papermill": {
     "duration": 0.019268,
     "end_time": "2024-08-22T10:22:26.379426",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.360158",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "def level_order(node):\n",
    "    q = deque()\n",
    "    \n",
    "    q.append(node)\n",
    "    \n",
    "    while q:\n",
    "        node = q.popleft()\n",
    "        print(node)\n",
    "        if node.left: q.append(node.left)\n",
    "        if node.right: q.append(node.right)\n",
    "            \n",
    "level_order(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c328c6e",
   "metadata": {
    "papermill": {
     "duration": 0.006338,
     "end_time": "2024-08-22T10:22:26.392498",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.386160",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "## Check if Value Exists (DFS) Time: O(n), Space: O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "94ca9ad4",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-22T10:22:26.408111Z",
     "iopub.status.busy": "2024-08-22T10:22:26.407606Z",
     "iopub.status.idle": "2024-08-22T10:22:26.419201Z",
     "shell.execute_reply": "2024-08-22T10:22:26.417876Z"
    },
    "papermill": {
     "duration": 0.02264,
     "end_time": "2024-08-22T10:22:26.421953",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.399313",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def search(node, target):\n",
    "    if not node:\n",
    "        return False\n",
    "    \n",
    "    if node.val == target:\n",
    "        return True\n",
    "    \n",
    "    return search(node.left, target) or search(node.right, target)\n",
    "\n",
    "search(a, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d42bec3",
   "metadata": {
    "papermill": {
     "duration": 0.006225,
     "end_time": "2024-08-22T10:22:26.434833",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.428608",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Binary Search Trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a452fffe",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-22T10:22:26.450882Z",
     "iopub.status.busy": "2024-08-22T10:22:26.449651Z",
     "iopub.status.idle": "2024-08-22T10:22:26.457981Z",
     "shell.execute_reply": "2024-08-22T10:22:26.456353Z"
    },
    "papermill": {
     "duration": 0.019252,
     "end_time": "2024-08-22T10:22:26.460643",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.441391",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "a2 = TreeNode(5)\n",
    "b2 = TreeNode(1)\n",
    "c2 = TreeNode(8)\n",
    "d2 = TreeNode(-1)\n",
    "e2 = TreeNode(3)\n",
    "f2 = TreeNode(7)\n",
    "g2 = TreeNode(9)\n",
    "\n",
    "\n",
    "a2.left, a2.right = b2, c2\n",
    "b2.left, b2.right = d2, e2\n",
    "c2.left, c2.right = f2, g2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "eab68ca5",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-22T10:22:26.475846Z",
     "iopub.status.busy": "2024-08-22T10:22:26.475390Z",
     "iopub.status.idle": "2024-08-22T10:22:26.482630Z",
     "shell.execute_reply": "2024-08-22T10:22:26.481093Z"
    },
    "papermill": {
     "duration": 0.018512,
     "end_time": "2024-08-22T10:22:26.485783",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.467271",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1\n",
      "1\n",
      "3\n",
      "5\n",
      "7\n",
      "8\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "in_order(a2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a5a0186",
   "metadata": {
    "papermill": {
     "duration": 0.00683,
     "end_time": "2024-08-22T10:22:26.499616",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.492786",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "## Check if Value Exists (DFS) Time: O(log n), Space: O(log n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "277c366a",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-22T10:22:26.515722Z",
     "iopub.status.busy": "2024-08-22T10:22:26.515316Z",
     "iopub.status.idle": "2024-08-22T10:22:26.525911Z",
     "shell.execute_reply": "2024-08-22T10:22:26.524505Z"
    },
    "papermill": {
     "duration": 0.022016,
     "end_time": "2024-08-22T10:22:26.528652",
     "exception": false,
     "start_time": "2024-08-22T10:22:26.506636",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def search_bst(node, target):\n",
    "    if not node:\n",
    "        return False\n",
    "    \n",
    "    if node.val == target:\n",
    "        return True\n",
    "    \n",
    "    if target < node.val: \n",
    "        return search_bst(node.left, target)\n",
    "    \n",
    "    if target > node.val:\n",
    "        return search_bst(node.right, target)\n",
    "    \n",
    "search_bst(a2, 1)"
   ]
  }
 ],
 "metadata": {
  "kaggle": {
   "accelerator": "none",
   "dataSources": [],
   "dockerImageVersionId": 30761,
   "isGpuEnabled": false,
   "isInternetEnabled": true,
   "language": "python",
   "sourceType": "notebook"
  },
  "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.10.14"
  },
  "papermill": {
   "default_parameters": {},
   "duration": 4.328239,
   "end_time": "2024-08-22T10:22:27.060481",
   "environment_variables": {},
   "exception": null,
   "input_path": "__notebook__.ipynb",
   "output_path": "__notebook__.ipynb",
   "parameters": {},
   "start_time": "2024-08-22T10:22:22.732242",
   "version": "2.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}