Binary_Tree_Implimentations.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Binary Tree Basic Implimentations\n",
    "# For harder questions and answers, refer to:\n",
    "# https://github.com/volkansonmez/Algorithms-and-Data-Structures-1/blob/master/Binary_Tree_All_Methods.ipynb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[18, 1, 19, 8, 0, 6, 10, 17, 9, 7, 4, 2, 5, 13, 14, 11, 3, 12, 16, 15]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "np.random.seed(0)\n",
    "\n",
    "class BST():\n",
    "    def __init__(self, root = None):\n",
    "        self.root = root\n",
    "        \n",
    "     \n",
    "    def add_node(self, value):\n",
    "        if self.root == None:\n",
    "            self.root = Node(value)\n",
    "        else:\n",
    "            self._add_node(self.root, value)\n",
    "        \n",
    "    \n",
    "    def _add_node(self, key_node, value):\n",
    "        if key_node == None: return\n",
    "        if value < key_node.cargo: # go left\n",
    "            if key_node.left == None:\n",
    "                key_node.left = Node(value)\n",
    "                key_node.left.parent = key_node\n",
    "            else:\n",
    "                self._add_node(key_node.left, value)\n",
    "            \n",
    "        elif value > key_node.cargo: # go right\n",
    "            if key_node.right == None:\n",
    "                key_node.right = Node(value)\n",
    "                key_node.right.parent = key_node\n",
    "            else:\n",
    "                self._add_node(key_node.right, value)\n",
    "                \n",
    "        else: # if the value already exists\n",
    "            return\n",
    "        \n",
    "        \n",
    "    def add_random_nodes(self):\n",
    "        numbers = np.arange(0,20)\n",
    "        self.random_numbers = np.random.permutation(numbers)\n",
    "        for i in self.random_numbers:\n",
    "            self.add_node(i)\n",
    "                \n",
    "        \n",
    "    def find_node(self, value): # find if the value exists in the tree\n",
    "        if self.root == None: return None\n",
    "        if self.root.cargo == value: \n",
    "            return self.root\n",
    "        else:\n",
    "            return self._find_node(self.root, value)\n",
    "                \n",
    "                \n",
    "    def _find_node(self, key_node, value):\n",
    "        if key_node == None: return None\n",
    "        if key_node.cargo == value: return key_node\n",
    "        if value < key_node.cargo: # go left\n",
    "            key_node = key_node.left\n",
    "            return self._find_node(key_node, value)\n",
    "        else:\n",
    "            key_node = key_node.right\n",
    "            return self._find_node(key_node, value)\n",
    "        \n",
    "        \n",
    "    def print_in_order(self): # do a dfs, print from left leaf to the right leaf\n",
    "        if self.root == None: return\n",
    "        key_node = self.root\n",
    "        self._print_in_order(key_node)\n",
    "        \n",
    "    \n",
    "    def _print_in_order(self, key_node):\n",
    "        if key_node == None: return\n",
    "        self._print_in_order(key_node.left)\n",
    "        print(key_node.cargo, end = ' ')\n",
    "        self._print_in_order(key_node.right)\n",
    "        \n",
    "       \n",
    "    def print_leaf_nodes_by_stacking(self):\n",
    "        all_nodes = [] # append the node objects\n",
    "        leaf_nodes = [] # append the cargos of the leaf nodes\n",
    "        if self.root == None: return None\n",
    "        all_nodes.append(self.root)\n",
    "        while len(all_nodes) > 0:\n",
    "            curr_node = all_nodes.pop() # pop the last item, last in first out\n",
    "            if curr_node.left != None:\n",
    "                all_nodes.append(curr_node.left)\n",
    "            if curr_node.right != None:\n",
    "                all_nodes.append(curr_node.right)\n",
    "            elif curr_node.left == None and curr_node.right == None:\n",
    "                leaf_nodes.append(curr_node.cargo)\n",
    "        return leaf_nodes  \n",
    "    \n",
    "        \n",
    "        \n",
    "    def print_bfs(self, todo = None):\n",
    "        if todo == None: todo = []\n",
    "        if self.root == None: return\n",
    "        todo.append(self.root)\n",
    "        while len(todo) > 0:\n",
    "            curr_node = todo.pop()\n",
    "            if curr_node.left != None:\n",
    "                todo.append(curr_node.left)\n",
    "            if curr_node.right != None:\n",
    "                todo.append(curr_node.right)\n",
    "            print(curr_node.cargo, end = ' ')\n",
    "        \n",
    "        \n",
    "        \n",
    "    def find_height(self):\n",
    "        if self.root == None: return 0\n",
    "        else:\n",
    "            return self._find_height(self.root, left = 0, right = 0)\n",
    "            \n",
    "    \n",
    "    def _find_height(self, key_node, left, right):\n",
    "        if key_node == None: return max(left, right)\n",
    "        return self._find_height(key_node.left, left + 1, right)\n",
    "        return self._find_height(key_node.right, left, right +1)\n",
    "\n",
    "        \n",
    "        \n",
    "    def is_valid(self):\n",
    "        if self.root == None: return True\n",
    "        key_node = self.root\n",
    "        return self._is_valid(self.root, -np.inf, np.inf)\n",
    "        \n",
    "        \n",
    "    def _is_valid(self, key_node, min_value , max_value):\n",
    "        if key_node == None: return True\n",
    "        if key_node.cargo > max_value or key_node.cargo < min_value: return False\n",
    "        left_valid = True\n",
    "        right_valid = True\n",
    "        if key_node != None and key_node.left != None:\n",
    "            left_valid = self._is_valid(key_node.left, min_value, key_node.cargo)\n",
    "        if key_node != None and key_node.right != None:\n",
    "            right_valid = self._is_valid(key_node.right, key_node.cargo, max_value)\n",
    "        return left_valid and right_valid\n",
    "        \n",
    "        \n",
    "    def zig_zag_printing_top_to_bottom(self):\n",
    "        if self.root == None: return\n",
    "        even_stack = [] # stack the nodes in levels that are in even numbers\n",
    "        odd_stack = [] # stack the nodes in levels that are in odd numbers\n",
    "        print_nodes = [] # append the items' cargos in zigzag order\n",
    "        even_stack.append(self.root)\n",
    "        while len(even_stack) > 0 or len(odd_stack) > 0:\n",
    "            \n",
    "            while len(even_stack) > 0:\n",
    "                tmp = even_stack.pop()\n",
    "                print_nodes.append(tmp.cargo)\n",
    "                if tmp.right != None:\n",
    "                    odd_stack.append(tmp.right)\n",
    "                if tmp.left != None:\n",
    "                    odd_stack.append(tmp.left)\n",
    "    \n",
    "    \n",
    "            while len(odd_stack) > 0:\n",
    "                tmp = odd_stack.pop()\n",
    "                print_nodes.append(tmp.cargo)\n",
    "                if tmp.left != None:\n",
    "                    even_stack.append(tmp.left)\n",
    "                if tmp.right != None:\n",
    "                    even_stack.append(tmp.right)\n",
    "        \n",
    "        return print_nodes\n",
    "        \n",
    "        \n",
    "        \n",
    "    def lowest_common_ancestor(self, node1, node2): # takes two cargos and prints the lca node of them \n",
    "        if self.root == None: return\n",
    "        node1_confirm = self.find_node(node1)\n",
    "        if node1_confirm == None: return\n",
    "        node2_confirm = self.find_node(node2)\n",
    "        if node2_confirm == None: return\n",
    "        key_node = self.root\n",
    "        print('nodes are in the tree')\n",
    "        return self._lowest_common_ancestor(key_node, node1, node2)\n",
    "    \n",
    "    \n",
    "    def _lowest_common_ancestor(self, key_node, node1, node2):\n",
    "        if key_node == None: return\n",
    "        if node1 < key_node.cargo and node2 < key_node.cargo:\n",
    "            key_node = key_node.left\n",
    "            return self._lowest_common_ancestor(key_node, node1, node2)\n",
    "        elif node1 > key_node.cargo and node2 > key_node.cargo:\n",
    "            key_node = key_node.right\n",
    "            return self._lowest_common_ancestor(key_node, node1, node2)\n",
    "        else:\n",
    "            return key_node , key_node.cargo\n",
    "        \n",
    "            \n",
    "    def maximum_path_sum(self): # function to find the maximum path sum\n",
    "        if self.root == None: return\n",
    "        max_value = -np.inf\n",
    "        return self._maximum_path_sum(self.root, max_value)\n",
    "        \n",
    "        \n",
    "    def _maximum_path_sum(self, key_node, max_value): # recursive function to search and return the max path sum\n",
    "        if key_node == None: return 0\n",
    "        left = self._maximum_path_sum(key_node.left, max_value)\n",
    "        right = self._maximum_path_sum(key_node.right, max_value)\n",
    "        max_value = max(max_value, key_node.cargo + left + right)\n",
    "        return max(left, right) + self.root.cargo\n",
    "            \n",
    "            \n",
    "        \n",
    "class Node():\n",
    "    def __init__(self, cargo = None, parent = None, left = None, right = None):\n",
    "            self.cargo = cargo\n",
    "            self.parent = parent\n",
    "            self.left = left\n",
    "            self.right = right\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "test_bst = BST()\n",
    "test_bst.add_random_nodes()\n",
    "#print(test_bst.print_in_order())\n",
    "#test_bst.find_node(11)\n",
    "#test_bst.print_leaf_nodes_by_stacking()\n",
    "#test_bst.print_bfs()   \n",
    "#test_bst.find_height()\n",
    "#test_bst.is_valid()\n",
    "test_bst.zig_zag_printing_top_to_bottom()\n",
    "#test_bst.lowest_common_ancestor(8, 0)\n",
    "#test_bst.maximum_path_sum()"
   ]
  },
  {
   "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": 2
}