Trees/Tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Author: OMKAR PATHAK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* A tree is a data structure similar to a linked List but instead of each node pointing simply to the next node in a linear fashion, each node points to a number of nodes. Tree is an example of non-linear data structures. A tree structure is a way of representing the **hierarchical** nature of a structure in a graphical form.\n",
    "* The **root** of the tree is the node with no parents. There can be at most one root node in a tree.\n",
    "* The _edge_ refers to the link from parent to child.\n",
    "* A node with NO children is called _leaf_ node.\n",
    "* Children of same parent are called _siblings_.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Applications of trees:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*  Manipulate hierarchical data.\n",
    "* Make information easy to search (see tree traversal).\n",
    "* Manipulate sorted lists of data.\n",
    "* As a workflow for compositing digital images for visual effects.\n",
    "* Router algorithms\n",
    "* Form of a multi-stage decision-making (see business chess)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* A tree is called _binary tree_ if each node of the tree has zero, one or two children.\n",
    "* Empty tree is also a valid binary tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Types of binary trees:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **Full binary tree**:\n",
    "A Binary Tree is full if every node has 0 or 2 children. Following are examples of full binary tree.\n",
    "2. **Complete binary tree**:\n",
    "A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible.\n",
    "3. **Perfect Binary Tree**:\n",
    "A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.\n",
    "4. **Balanced Binary Tree**:\n",
    "A binary tree is balanced if height of the tree is O(Log n) where n is number of nodes. For Example, AVL tree maintain O(Log n) height by making sure that the difference between heights of left and right subtrees is 1. Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf paths are same and there are no adjacent red nodes. Balanced Binary Search trees are performance wise good as they provide O(log n) time for search, insert and delete.\n",
    "5. **A degenerate (or pathological) tree**:\n",
    "A Tree where every internal node has one child. Such trees are performance-wise same as linked list.\n",
    "\n",
    "For visualizations:\n",
    "http://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/\n",
    "\n",
    "For properties:\n",
    "http://www.geeksforgeeks.org/binary-tree-set-2-properties/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary tree implementation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "' This will a create like this \\n                    1\\n                /                   2            3\\n        /\\n    4\\n'"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, data = None):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.data = data\n",
    "    \n",
    "    # for setting left node\n",
    "    def setLeft(self, node):\n",
    "        self.left = node\n",
    "    \n",
    "    # for setting right node\n",
    "    def setRight(self, node):\n",
    "        self.right = node\n",
    "        \n",
    "    # for getting the left node\n",
    "    def getLeft(self):\n",
    "        return self.left\n",
    "    \n",
    "    # for getting right node\n",
    "    def getRight(self):\n",
    "        return self.right\n",
    "    \n",
    "    # for setting data of a node\n",
    "    def setData(self, data):\n",
    "        self.data = data\n",
    "        \n",
    "    # for getting data of a node\n",
    "    def getData(self):\n",
    "        return self.data\n",
    "    \n",
    "root = Node(1)\n",
    "root.setLeft(Node(2))\n",
    "root.setRight(Node(3))\n",
    "root.left.setLeft(Node(4))\n",
    "''' This will a create like this \n",
    "                    1\n",
    "                /       \\\n",
    "            2            3\n",
    "        /\n",
    "    4\n",
    "'''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tree traversal:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. Following are the generally used ways for traversing trees.\n",
    "\n",
    "* Inorder     (left, data, right)\n",
    "* Preorder   (data, left, right)\n",
    "* Postorder (left, right, data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementing tree traversals:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Inorder  Traversal:\n",
      "4 2 1 3 \n",
      "Preorder Traversal:\n",
      "1 2 4 3 \n",
      "Postorder Traversal:\n",
      "4 2 3 1 "
     ]
    }
   ],
   "source": [
    "# in this we traverse first to the leftmost node, then print its data and then traverse for rightmost node\n",
    "def inorder(Tree):\n",
    "    if Tree:\n",
    "        inorder(Tree.getLeft())\n",
    "        print(Tree.getData(), end = ' ')\n",
    "        inorder(Tree.getRight())\n",
    "    return\n",
    "\n",
    "# in this we first print the root node and then traverse towards leftmost node and then to the rightmost node\n",
    "def preorder(Tree):\n",
    "    if Tree:\n",
    "        print(Tree.getData(), end = ' ')\n",
    "        preorder(Tree.getLeft())\n",
    "        preorder(Tree.getRight())\n",
    "    return \n",
    "\n",
    "# in this we first traverse to the leftmost node and then to the rightmost node and then print the data\n",
    "def postorder(Tree):\n",
    "    if Tree:\n",
    "        postorder(Tree.getLeft())\n",
    "        postorder(Tree.getRight())\n",
    "        print(Tree.getData(), end = ' ')\n",
    "    return\n",
    "\n",
    "print('Inorder  Traversal:')\n",
    "inorder(root)\n",
    "print('\\nPreorder Traversal:')\n",
    "preorder(root)\n",
    "print('\\nPostorder Traversal:')\n",
    "postorder(root)      "
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}