Binary_Tree_All_Methods.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Answers to common coding questions on BST "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "class BST():\n",
    "    def __init__(self, root = None):\n",
    "        self.root = root\n",
    "       \n",
    "    \n",
    "    def add_node(self, value): # add node to a binary tree\n",
    "        if self.root == None:\n",
    "            self.root = Node(value)\n",
    "        else:\n",
    "            key_node = self.root\n",
    "            self._add_node(self.root, value)\n",
    "        \n",
    "    \n",
    "    def _add_node(self, key_node, value): # recursive function to place the nodes in place\n",
    "        if key_node == None: return\n",
    "        if value < key_node.cargo: # go left\n",
    "            if key_node.leftchild == None:\n",
    "                key_node.leftchild = Node(value)\n",
    "                key_node.leftchild.parent = key_node\n",
    "            else:\n",
    "                self._add_node(key_node.leftchild, value)\n",
    "        elif value > key_node.cargo:\n",
    "            if key_node.rightchild == None:\n",
    "                key_node.rightchild = Node(value)\n",
    "                key_node.rightchild.parent = key_node\n",
    "            else:\n",
    "                self._add_node(key_node.rightchild, value)\n",
    "        else: # if the value exists, do not add\n",
    "            return\n",
    "    \n",
    "    \n",
    "    def add_bunch_of_nodes_to_the_tree(self): # add random nodes to a binary tree\n",
    "        nodes = np.arange(25)\n",
    "        shuffled_nodes = np.random.permutation(nodes)\n",
    "        for i in shuffled_nodes: \n",
    "            self.add_node(i)\n",
    "        \n",
    "        \n",
    "    def create_a_V_tree(self): # create random numbers and add them to a V shape tree, one root, two leaves only\n",
    "        random_numbers = np.arange(25)\n",
    "        shuffled_nodes = np.random.permutation(random_numbers)\n",
    "        for i in shuffled_nodes:\n",
    "            self.create_a_V_shape_tree(i)\n",
    "    \n",
    "    \n",
    "    def create_a_V_shape_tree(self, value): # create a V shape tree\n",
    "        if self.root == None:\n",
    "            self.root = Node(value)\n",
    "        else:\n",
    "            key_node = self.root\n",
    "            self._create_a_V_shape_tree(key_node, value)\n",
    "\n",
    "    \n",
    "    def _create_a_V_shape_tree(self, key_node, value): # add nodes recursively to a V shape tree\n",
    "        if key_node == None: return\n",
    "        # split rules:\n",
    "        if value < key_node.cargo: # go left on bst\n",
    "            if key_node.leftchild == None: # if leftchild is None\n",
    "                key_node.leftchild = Node(value)\n",
    "                key_node.leftchild.parent = key_node\n",
    "            elif value > key_node.leftchild.cargo: # squeeze the new node in between key_node and its leftchild\n",
    "                new_node = Node(value)\n",
    "                key_node.leftchild.parent = new_node\n",
    "                new_node.leftchild = key_node.leftchild\n",
    "                key_node.leftchild = new_node\n",
    "                new_node.parent = key_node\n",
    "            else: # if value is smaller than the leftchild's cargo\n",
    "                key_node = key_node.leftchild\n",
    "                self._create_a_V_shape_tree(key_node, value)\n",
    "        elif value > key_node.cargo: # go right on bst\n",
    "            if key_node.rightchild == None:\n",
    "                key_node.rightchild = Node(value)\n",
    "                key_node.rightchild.parent = key_node\n",
    "            elif value < key_node.rightchild.cargo: # squeeze the new node in between key_node and its rightchild\n",
    "                new_node = Node(value)\n",
    "                key_node.rightchild.parent = new_node\n",
    "                new_node.rightchild = key_node.rightchild\n",
    "                key_node.rightchild = new_node\n",
    "                new_node.parent = key_node\n",
    "            else: # if the value is bigger than the rightchild's cargo\n",
    "                key_node = key_node.rightchild\n",
    "                self._create_a_V_shape_tree(key_node, value)\n",
    "        else: # if the value exists already\n",
    "            # print('The value already exists')\n",
    "            return\n",
    "            \n",
    "        \n",
    "        \n",
    "    def find_node(self, value): # return the node object\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): # find and return the node recursively (not the cargo)\n",
    "        if key_node == None: return None\n",
    "        if value == key_node.cargo: return key_node\n",
    "        if value < key_node.cargo:\n",
    "            return self._find_node(key_node.leftchild, value)\n",
    "        else:\n",
    "            return self._find_node(key_node.rightchild, value)\n",
    "        \n",
    "    \n",
    "            \n",
    "    def print_in_order(self): # from left bottom leaf to the right bottom leaf, print all nodes \n",
    "        if self.root == None: return\n",
    "        else:\n",
    "            self._print_in_order(self.root)\n",
    "            \n",
    "    \n",
    "    def _print_in_order(self, key_node): # recursive function to print the nodes in order\n",
    "        if key_node != None:\n",
    "            self._print_in_order(key_node.leftchild)\n",
    "            print(key_node.cargo)\n",
    "            self._print_in_order(key_node.rightchild)\n",
    "    \n",
    "    \n",
    "    def list_all_nodes_in_order(self): # similar to print_in_order method, return a list of cargos in order\n",
    "        all_nodes = []\n",
    "        if self.root == None: return\n",
    "        else:\n",
    "            return self._list_all_nodes_in_order(all_nodes, self.root)\n",
    "        \n",
    "        \n",
    "    def _list_all_nodes_in_order(self, all_nodes, key_node): # recursive function to return the list of cargos\n",
    "        if key_node != None:\n",
    "            self._list_all_nodes_in_order(all_nodes, key_node.leftchild)\n",
    "            all_nodes.append(key_node.cargo)\n",
    "            self._list_all_nodes_in_order(all_nodes, key_node.rightchild)\n",
    "        return all_nodes\n",
    "        \n",
    "        \n",
    "    def print_left_side(self): # print left side of the tree\n",
    "        if self.root == None: return \n",
    "        else:\n",
    "            self._print_left_side(self.root)\n",
    "            \n",
    "            \n",
    "    def _print_left_side(self, key_node): # recursively percolate down and print the leftchilds\n",
    "        if key_node == None: return\n",
    "        self._print_left_side(key_node.leftchild)\n",
    "        print(key_node.cargo , end = \" \")\n",
    "        \n",
    "    \n",
    "    def print_leaf_nodes_in_order_by_stacking(self): # alternative methodf to print the nodes in order\n",
    "        all_nodes = [] # Stack to store all the nodes # of tree  \n",
    "        leaf_nodes = [] # Stack to store all the # leaf nodes  \n",
    "        \n",
    "        all_nodes.append(self.root)  # Push the root node  \n",
    "\n",
    "        while len(all_nodes) > 0:  \n",
    "            key_node = all_nodes.pop()   \n",
    "            if key_node.leftchild: \n",
    "                all_nodes.append(key_node.leftchild) \n",
    "            if key_node.rightchild:  \n",
    "                all_nodes.append(key_node.rightchild)  \n",
    "                \n",
    "            elif key_node.leftchild == None and key_node.rightchild == None:\n",
    "                leaf_nodes.append(key_node.cargo)  \n",
    "\n",
    "        return leaf_nodes\n",
    "\n",
    "            \n",
    "    def print_leaf_nodes_in_order(self): # dfs to print nodes in order from left leaf to the right leaf\n",
    "        if self.root == None: return\n",
    "        else:\n",
    "            self._print_leaf_nodes_in_order(self.root)\n",
    "            \n",
    "    \n",
    "    def _print_leaf_nodes_in_order(self, key_node): # recursively go left, print the leaf node, go right\n",
    "        if key_node != None:\n",
    "            self._print_leaf_nodes_in_order(key_node.leftchild)\n",
    "            if key_node.leftchild == None and key_node.rightchild == None:\n",
    "                print(key_node.cargo)\n",
    "            self._print_leaf_nodes_in_order(key_node.rightchild)\n",
    "       \n",
    "    \n",
    "    def find_height_of_bst(self): # finding the height of the BST\n",
    "        if self.root == None: return 0\n",
    "        else:\n",
    "            leftheight, rightheight = 0, 0\n",
    "            key_node = self.root\n",
    "            return self._find_height_of_bst(key_node, leftheight, rightheight)\n",
    "    \n",
    "    \n",
    "    def _find_height_of_bst(self, key_node, leftheight, rightheight): # recursive function to return the height of BST\n",
    "        if key_node == None: \n",
    "            return max(leftheight, rightheight)\n",
    "        else:\n",
    "            return self._find_height_of_bst(key_node.leftchild , leftheight + 1, rightheight)\n",
    "            return self._find_height_of_bst(key_node.rightchild, leftheight, rightheight + 1)  \n",
    "    \n",
    "    \n",
    "    def print_height(self): # function to print the height\n",
    "        height_of_tree = self.find_height_of_bst()\n",
    "        print('the height of the tree is: {}'.format(height_of_tree))\n",
    "    \n",
    "    \n",
    "    def height_balance(self): # height method to find if the tree is height balanced \n",
    "        if self.root == None: return 0\n",
    "        left_branch = self.root.leftchild\n",
    "        right_branch = self.root.rightchild\n",
    "        return self.find_height(left_branch), self.find_height(right_branch)\n",
    "        \n",
    "    \n",
    "    def find_height(self, branch): # finding the height of the BST branch\n",
    "        if branch == None: return 0\n",
    "        else:\n",
    "            leftheight, rightheight = 0, 0\n",
    "            key_node = branch\n",
    "            return self._find_height_of_bst(key_node, leftheight, rightheight)\n",
    "    \n",
    "    \n",
    "    def _find_height_of_bst(self, key_node, leftheight, rightheight): # recursive function to return the height of BST\n",
    "        if key_node == None: \n",
    "            return max(leftheight, rightheight)\n",
    "        else:\n",
    "            return self._find_height_of_bst(key_node.leftchild , leftheight + 1, rightheight)\n",
    "            return self._find_height_of_bst(key_node.rightchild, leftheight, rightheight + 1)  \n",
    "    \n",
    "    \n",
    "    def print_height_balance(self): # print the height balance\n",
    "        left_and_right_heights = self.height_balance()\n",
    "        print('the height of left and right branches: {}'.format(left_and_right_heights))\n",
    "        \n",
    "    \n",
    "    def delete(self, value): # delete a node\n",
    "        node_to_be_deleted = self.find_node(value)\n",
    "        if node_to_be_deleted == None: return None\n",
    "        else:\n",
    "            return self._delete(node_to_be_deleted, value)\n",
    "    \n",
    "    \n",
    "    def _delete(self, key_node, value): # function to find the number of children and delete the node accordingly\n",
    "    \n",
    "        def find_children(key_node): # nested function to find the number of children\n",
    "            n = 0\n",
    "            if key_node.leftchild != None:\n",
    "                n +=1\n",
    "            if key_node.rightchild != None:\n",
    "                n +=1\n",
    "            return n\n",
    "        \n",
    "        number_of_children = find_children(key_node)\n",
    "        \n",
    "        \n",
    "        def find_min_in_tree(key_node): # find the min value in the tree\n",
    "            while key_node.leftchild != None:\n",
    "                key_node = key_node.leftchild\n",
    "            return key_node\n",
    "        \n",
    "        if key_node.rightchild != None:\n",
    "            successor = find_min_in_tree(key_node.rightchild)\n",
    "        \n",
    "        \n",
    "        # delete nodes for key_node having no children\n",
    "        if number_of_children == 0:\n",
    "            # it is a leaf node\n",
    "            if key_node.parent.leftchild == key_node:\n",
    "                key_node.parent.leftchild = None\n",
    "            else:\n",
    "                key_node.parent.rightchild = None\n",
    "                \n",
    "                \n",
    "        if number_of_children == 1:\n",
    "            # there are 4 cases:\n",
    "            # the node is parent's leftchild\n",
    "                # the node has leftchild\n",
    "            if key_node.parent.leftchild == key_node and key_node.leftchild != None:\n",
    "                key_node.parent.leftchild = key_node.leftchild\n",
    "                key_node.leftchild.parent = key_node.parent\n",
    "                # the node has rightchild\n",
    "            elif key_node.parent.leftchild == key_node and key_node.rightchild != None:\n",
    "                key_node.parent.leftchild = key_node.rightchild\n",
    "                key_node.rightchild.parent = key_node.parent\n",
    "            # the node is parent's rightchild\n",
    "                # the node has leftchild\n",
    "            elif key_node.parent.rightchild == key_node and key_node.leftchild != None:\n",
    "                key_node.parent.rightchild = key_node.leftchild\n",
    "                key_node.leftchild.parent = key_node.parent\n",
    "            else:\n",
    "                # the node has rightchild\n",
    "                key_node.parent.rightchild = key_node.rightchild\n",
    "                key_node.rightchild.parent = key_node.parent\n",
    "                \n",
    "                \n",
    "        if number_of_children == 2:\n",
    "            successor = find_min_in_tree(key_node.rightchild)\n",
    "            key_node.cargo = successor.cargo\n",
    "            successor = None\n",
    "        \n",
    "        \n",
    "    def is_valid(self): # check if the tree not only has validity for the value order between parent child nodes \n",
    "        if self.root == None: return True\n",
    "        else:\n",
    "            return self._is_valid(self.root, -np.inf, np.inf)\n",
    "\n",
    "        \n",
    "    def _is_valid(self, key_node, min, max): # recursive function to return the cargo values if between min and max\n",
    "        if key_node.cargo <= min or key_node.cargo >= max: return False\n",
    "        left_ok = True\n",
    "        right_ok = True\n",
    "        if key_node != None and key_node.leftchild != None:\n",
    "            left_ok = self._is_valid(key_node.leftchild, min, key_node.cargo)\n",
    "        if key_node != None and key_node.rightchild != None:\n",
    "            right_ok = self._is_valid(key_node.rightchild, key_node.cargo, max)\n",
    "        return left_ok and right_ok\n",
    "        \n",
    "        \n",
    "    def print_validity(self):  # function to print the validity of the bst\n",
    "        is_valid_bst = self.is_valid()\n",
    "        if is_valid_bst:\n",
    "            print('the bst is valid')\n",
    "        else:\n",
    "            print('the tree is not a bst')\n",
    "\n",
    "\n",
    "    def print_bfs(self):  # it is to print the nodes in vertical order, BFS\n",
    "        print('Starting the breadth first search printing')\n",
    "        if self.root == None: return None\n",
    "        key_node = self.root\n",
    "        self._print_bfs(self.root)\n",
    "           \n",
    "            \n",
    "    def _print_bfs(self, key_node, todo = None): # recursive function using stack to print each level of nodes\n",
    "        if todo == None: todo = []\n",
    "        if key_node == None: return \n",
    "        print(key_node.cargo)\n",
    "        if key_node.leftchild != None:\n",
    "            todo.append(key_node.leftchild)\n",
    "        if key_node.rightchild != None:\n",
    "            todo.append(key_node.rightchild)\n",
    "        if len(todo) > 0:\n",
    "            next_node = todo.pop(0)\n",
    "            self._print_bfs(next_node , todo)\n",
    "            \n",
    "            \n",
    "    def dfs(self): # print in order with depth first search \n",
    "        if self.root == None: return\n",
    "        else:\n",
    "            key_node = self.root\n",
    "            self.print_dfs(key_node)\n",
    "            \n",
    "            \n",
    "    def print_dfs(self, key_node): # recursive function to print the node cargos in order with DFS left to right\n",
    "        if key_node == None: return None\n",
    "        if key_node.leftchild != None: self.print_dfs(key_node.leftchild)\n",
    "        print(key_node.cargo)\n",
    "        if key_node.rightchild != None: self.print_dfs(key_node.rightchild)\n",
    "        \n",
    "    \n",
    "    def print_pre_order(self): # print the node cargos in pre-order \n",
    "        if self.root == None: return None\n",
    "        else:\n",
    "            self._print_pre_order(self.root)\n",
    "        \n",
    "    \n",
    "    def _print_pre_order(self, key_node, todo = None): # recursive function to print the nodes in pre-order\n",
    "        if todo == None: todo = []\n",
    "        if key_node == None: return \n",
    "        print(key_node.cargo)\n",
    "        if key_node.rightchild != None:\n",
    "            todo.insert(0, key_node.rightchild)\n",
    "        if key_node.leftchild != None:\n",
    "            todo.insert(0, key_node.leftchild)\n",
    "        if len(todo) > 0:\n",
    "            popped_item = todo.pop(0)\n",
    "            self._print_pre_order(popped_item, todo)\n",
    "            \n",
    "    \n",
    "    def zig_zag_printing_top_to_bottom(self): # spiral order printing using two stacks \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.rightchild != None:\n",
    "                    odd_stack.append(tmp.rightchild)\n",
    "                if tmp.leftchild != None:\n",
    "                    odd_stack.append(tmp.leftchild)\n",
    "    \n",
    "    \n",
    "            while len(odd_stack) > 0:\n",
    "                tmp = odd_stack.pop()\n",
    "                print_nodes.append(tmp.cargo)\n",
    "                if tmp.leftchild != None:\n",
    "                    even_stack.append(tmp.leftchild)\n",
    "                if tmp.rightchild != None:\n",
    "                    even_stack.append(tmp.rightchild)\n",
    "        \n",
    "        return print_nodes\n",
    "    \n",
    "    \n",
    "    def lowest_common_ancestor(self, node1, node2): # takes two cargos and prints the lca \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): # recursive function to return the lcs of two nodes\n",
    "        if key_node == None: return\n",
    "        if node1 < key_node.cargo and node2 < key_node.cargo:\n",
    "            key_node = key_node.leftchild\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.rightchild\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.leftchild, max_value)\n",
    "        right = self._maximum_path_sum(key_node.rightchild, 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",
    "    \n",
    "class Node():\n",
    "    def __init__(self, cargo, parent = None, leftchild = None, rightchild = None):\n",
    "        self.cargo = cargo\n",
    "        self.parent = parent\n",
    "        self.leftchild = leftchild\n",
    "        self.rightchild = rightchild\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "      \n",
    "test_bst = BST()\n",
    "#test_bst.add_node(30)\n",
    "test_bst.add_bunch_of_nodes_to_the_tree()\n",
    "#test_bst.print_height()\n",
    "#test_bst.print_in_order()\n",
    "#test_bst.print_validity()\n",
    "#test_bst.find_node(24)   \n",
    "#test_bst.delete(27)\n",
    "#test_bst.print_bfs()\n",
    "#test_bst.print_pre_order()\n",
    "#test_bst.print_dfs(test_bst.root)\n",
    "#test_bst.print_left_side()\n",
    "#test_bst.print_leaf_nodes_in_order_by_stacking()     \n",
    "test_bst.print_leaf_nodes_in_order()\n",
    "#test_bst.list_all_nodes_in_order()\n",
    "#test_bst.zig_zag_printing_top_to_bottom()\n",
    "#test_bst.print_height_balance()\n",
    "#test_bst.maximum_path_sum()\n",
    "#test_bst2 = BST() # this is going to be a V shaped structure, having 2 leaf nodes only.\n",
    "#test_bst2.create_a_V_tree()\n",
    "#test_bst2.print_leaf_nodes_in_order()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Notes on traversals: if 1 is root and 2, 3 are left and right children, and 4, 5 are left and right children of 2:\n",
    "#         1\n",
    "#     2       3\n",
    "# 4      5\n",
    "\n",
    "# Depth First Traversals:\n",
    "# (a) Inorder (Left, Root, Right) : 4 2 5 1 3  take a pen and paper and start from root drawing to the left leaf \n",
    "                        # write down when which node is visited second time (or it is a leaf), complete the map \n",
    "# (b) Preorder (Root, Left, Right) : 1 2 4 5 3  take a pen and paper and start from root drawing to the left leaf \n",
    "                        # write which node is visited, complete the map \n",
    "# (c) Postorder (Left, Right, Root) : 4 5 2 3 1  use pen and paper again, try to go to the leaves and print the leaves, \n",
    "                        # after the leaves are completed from left to right, the parent node can be printed\n",
    "\n",
    "# (d) Breadth First or Level Order Traversal : 1 2 3 4 5  layers printed in level order\n",
    "\n",
    "# to visualize them : https://www.youtube.com/watch?v=WLvU5EQVZqY"
   ]
  }
 ],
 "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
}