binary_tree_search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/tomascufaro/searchalgorithms_python/blob/main/binary_tree_search.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## binary tree \n",
    "\n",
    "A binary Search Tree is a node-based binary tree data structure which has the following properties:  \n",
    "\n",
    "- The left subtree of a node contains only nodes with keys lesser than the node’s key.\n",
    "- The right subtree of a node contains only nodes with keys greater than the node’s key.\n",
    "- The left and right subtree each must also be a binary search tree. \n",
    "- There must be no duplicate nodes.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "import random \n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function for searching in a binary tree class "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mFailed to start the Kernel. \n",
      "\u001b[1;31mKernel Python 3.9.6 64-bit is not usable. Check the Jupyter output tab for more information. \n",
      "\u001b[1;31mView Jupyter <a href='command:jupyter.viewOutput'>log</a> for further details."
     ]
    }
   ],
   "source": [
    "# A utility function to search a given key in BST\n",
    "def search(root,key):\n",
    "\t\n",
    "\t# Base Cases: root is null or key is present at root\n",
    "\tif root is None or root.val == key:\n",
    "\t\treturn root\n",
    "\n",
    "\t# Key is greater than root's key\n",
    "\tif root.val < key:\n",
    "\t\treturn search(root.right,key)\n",
    "\n",
    "\t# Key is smaller than root's key\n",
    "\treturn search(root.left,key)\n",
    "\n",
    "# This code is contributed by Bhavya Jain\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Time complexity**: O(h), where h is the height of the BST.\n",
    "- **Space complexity**: O(h), where h is the height of the BST. This is because the maximum amount of space needed to store the recursion stack would be h."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Python program to demonstrate\n",
    "# insert operation in binary search tree\n",
    "\n",
    "# A utility class that represents\n",
    "# an individual node in a BST\n",
    "\n",
    "\n",
    "class Node:\n",
    "\tdef __init__(self, key):\n",
    "        #this will be another node class type Node. That's how we build the recursive tree. \n",
    "\t\tself.left = None\n",
    "        #this will be or None or type Node \n",
    "\t\tself.right = None\n",
    "\t\tself.val = key\n",
    "\n",
    "# A utility function to insert\n",
    "# a new node with the given key\n",
    "\n",
    "\n",
    "def insert(root, key):\n",
    "\tif root is None:\n",
    "\t\treturn Node(key)\n",
    "\telse:\n",
    "\t\tif root.val == key:\n",
    "\t\t\treturn root\n",
    "\t\telif root.val < key:\n",
    "\t\t\troot.right = insert(root.right, key)\n",
    "\t\telse:\n",
    "\t\t\troot.left = insert(root.left, key)\n",
    "\treturn root\n",
    "\n",
    "# A utility function to do inorder tree traversal\n",
    "\n",
    "\n",
    "def inorder(root):\n",
    "\tif root:\n",
    "\t\tinorder(root.left)\n",
    "\t\tprint(root.val)\n",
    "\t\tinorder(root.right)\n",
    "\n",
    "\n",
    "# Driver program to test the above functions\n",
    "# Let us create the following BST\n",
    "# 50\n",
    "# /\t \\\n",
    "# 30\t 70\n",
    "# / \\ / \\\n",
    "# 20 40 60 80\n",
    "\n",
    "r = Node(50)\n",
    "r = insert(r, 30)\n",
    "r = insert(r, 20)\n",
    "r = insert(r, 40)\n",
    "r = insert(r, 70)\n",
    "r = insert(r, 60)\n",
    "r = insert(r, 80)\n",
    "\n",
    "# Print inoder traversal of the BST\n",
    "inorder(r)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "insertion using the loop "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GFG:\n",
    "    @staticmethod\n",
    "    def main(args):\n",
    "        tree = BST()\n",
    "        tree.insert(30)\n",
    "        tree.insert(50)\n",
    "        tree.insert(15)\n",
    "        tree.insert(20)\n",
    "        tree.insert(10)\n",
    "        tree.insert(40)\n",
    "        tree.insert(60)\n",
    "        tree.inorder()\n",
    " \n",
    " \n",
    "class Node:\n",
    "    left = None\n",
    "    val = 0\n",
    "    right = None\n",
    " \n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    " \n",
    " \n",
    "class BST:\n",
    "    root = None\n",
    " \n",
    "    def insert(self, key):\n",
    "        node = Node(key)\n",
    "        if (self.root == None):\n",
    "            self.root = node\n",
    "            return\n",
    "        prev = None\n",
    "        temp = self.root\n",
    "        while (temp != None):\n",
    "            if (temp.val > key):\n",
    "                prev = temp\n",
    "                temp = temp.left\n",
    "            elif(temp.val < key):\n",
    "                prev = temp\n",
    "                temp = temp.right\n",
    "        if (prev.val > key):\n",
    "            prev.left = node\n",
    "        else:\n",
    "            prev.right = node\n",
    " \n",
    "    def inorder(self):\n",
    "        temp = self.root\n",
    "        stack = []\n",
    "        while (temp != None or not (len(stack) == 0)):\n",
    "            if (temp != None):\n",
    "                stack.append(temp)\n",
    "                temp = temp.left\n",
    "            else:\n",
    "                temp = stack.pop()\n",
    "                print(str(temp.val) + \" \", end=\"\")\n",
    "                temp = temp.right\n",
    " \n",
    " \n",
    "if __name__ == \"__main__\":\n",
    "    GFG.main([])\n",
    " "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.6 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.9.6"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}