Trees and Tree Algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# List of Lists Representation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/smalltree.png \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]\n",
      "('left subtree = ', ['b', ['d', [], []], ['e', [], []]])\n",
      "('root = ', 'a')\n",
      "('right subtree = ', ['c', ['f', [], []], []])\n"
     ]
    }
   ],
   "source": [
    "myTree = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]\n",
    "print(myTree)\n",
    "print('left subtree = ', myTree[1])\n",
    "print('root = ', myTree[0])\n",
    "print('right subtree = ', myTree[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Construct a Binary Tree through list of lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def BinaryTree(r):\n",
    "    return [r,[],[]]\n",
    "\n",
    "def insertLeft(root,newBranch):\n",
    "    t=root.pop(1)\n",
    "    if(len(t)>1):\n",
    "        root.insert(1,[newBranch,t,[]])\n",
    "    else:\n",
    "        root.insert(1,[newBranch,[],[]])\n",
    "    \n",
    "    return root\n",
    "\n",
    "def insertRight(root,newBranch):\n",
    "    t=root.pop(2)\n",
    "    if(len(t)>1):\n",
    "        root.insert(2,[newBranch,[],t])\n",
    "    else:\n",
    "        root.insert(2,[newBranch,[],[]])\n",
    "        \n",
    "    return root\n",
    "\n",
    "def getRootVal(root):\n",
    "    return root[0]\n",
    "\n",
    "def getLeftChild(root):\n",
    "    return root[1]\n",
    "\n",
    "def getRightChild(root):\n",
    "    return root[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['c', ['f', [], []], []]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myTree=BinaryTree('a')\n",
    "insertLeft(myTree,'b')\n",
    "insertRight(myTree,'c')\n",
    "insertLeft(getLeftChild(myTree),'d')\n",
    "insertRight(getLeftChild(myTree),'e')\n",
    "insertLeft(getRightChild(myTree),'f')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Nodes and References"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "BinaryTree node class:\n",
    "\n",
    "* __init__: constructor\n",
    "* insertLeft: insert left child\n",
    "* insertRight: insert right child\n",
    "* getRightChild\n",
    "* getLeftChild\n",
    "* getRootVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class BinaryTree:\n",
    "    def __init__(self,rootObj):\n",
    "        self.key=rootObj\n",
    "        self.leftChild=None\n",
    "        self.rightChild=None\n",
    "        \n",
    "    def insertLeft(self,newNode):\n",
    "        if self.leftChild==None:\n",
    "            self.leftChild=BinaryTree(newNode)\n",
    "        else:\n",
    "            t=BinaryTree(newNode)\n",
    "            t.leftChild=self.leftChild\n",
    "            self.leftChild=t\n",
    "        \n",
    "    def insertRight(self,newNode):\n",
    "        if self.rightChild==None:\n",
    "            self.rightChild=BinaryTree(newNode)\n",
    "        else:\n",
    "            t=BinaryTree(newNode)\n",
    "            t.rightChild=self.rightChild\n",
    "            self.rightChild=t\n",
    "        \n",
    "    def getLeftChild(self):\n",
    "        return self.leftChild\n",
    "        \n",
    "    def getRightChild(self):\n",
    "        return self.rightChild\n",
    "        \n",
    "    def getRootVal(self):\n",
    "        return self.key\n",
    "        \n",
    "    def printTree(self,rootNode):\n",
    "        if(rootNode!=None):\n",
    "            print rootNode.key\n",
    "        if(rootNode.getLeftChild()!=None):\n",
    "            self.printTree(rootNode.getLeftChild())\n",
    "        if(rootNode.getRightChild()!=None):\n",
    "            self.printTree(rootNode.getRightChild())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "b\n",
      "d\n",
      "e\n",
      "c\n",
      "f\n"
     ]
    }
   ],
   "source": [
    "tree=BinaryTree('a')\n",
    "tree.insertLeft('b')\n",
    "tree.insertRight('c')\n",
    "tree.getLeftChild().insertLeft('d')\n",
    "tree.getLeftChild().insertRight('e')\n",
    "tree.getRightChild().insertLeft('f')\n",
    "tree.printTree(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Check if two Binary Trees are the same"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def MatchTree(t1,t2):\n",
    "    if(t1.key==t2.key):\n",
    "        # check left subtree\n",
    "        if(t1.getLeftChild()!=None and t2.getLeftChild()!=None):\n",
    "            leftmatch=MatchTree(t1.getLeftChild(),t2.getLeftChild())\n",
    "        elif(t1.getLeftChild()==None and t2.getLeftChild()==None):\n",
    "            leftmatch=True\n",
    "        else:\n",
    "            leftmatch=False\n",
    "        # check right subtree\n",
    "        if(t1.getRightChild()!=None and t2.getRightChild()!=None):\n",
    "            rightmatch=MatchTree(t1.getRightChild(),t2.getRightChild())\n",
    "        elif(t1.getRightChild()==None and t2.getRightChild()==None):\n",
    "            rightmatch=True\n",
    "        else:\n",
    "            rightmatch=False\n",
    "        return leftmatch and rightmatch\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree1=BinaryTree('a')\n",
    "tree1.insertLeft('b')\n",
    "tree1.insertRight('c')\n",
    "tree1.getLeftChild().insertLeft('d')\n",
    "tree1.getLeftChild().insertRight('e')\n",
    "tree1.getRightChild().insertLeft('f')\n",
    "tree2=BinaryTree('a')\n",
    "tree2.insertLeft('b')\n",
    "tree2.insertRight('c')\n",
    "tree2.getLeftChild().insertLeft('d')\n",
    "tree2.getRightChild().insertLeft('g')\n",
    "tree2.getLeftChild().insertRight('e')\n",
    "MatchTree(tree1,tree2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Priority Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A priority queue acts like a queue in that you dequeue an item by removing it from the front. However, in a priority queue the logical order of items inside a queue is determined by their priority. The highest priority items are at the front of the queue and the lowest priority items are at the back. Thus when you enqueue an item on a priority queue, the new item may move all the way to the front. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Heap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The basic operations we will implement for our binary heap are as follows:\n",
    "\n",
    "* BinaryHeap() creates a new, empty, binary heap.\n",
    "* insert(k) adds a new item to the heap.\n",
    "* findMin() returns the item with the minimum key value, leaving item in the heap.\n",
    "* delMin() returns the item with the minimum key value, removing the item from the heap.\n",
    "* isEmpty() returns true if the heap is empty, false otherwise.\n",
    "* size() returns the number of items in the heap.\n",
    "* buildHeap(list) builds a new heap from a list of keys."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "BinarySearchTree:\n",
    "\n",
    "* __init__: constructor\n",
    "* add: add a TreeNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    \n",
    "    def __init__(self,data,leftChild=None,rightChild=None):\n",
    "        self.data=data\n",
    "        self.leftChild=leftChild\n",
    "        self.rightChild=rightChild"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class BinarySearchTree:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.root=None\n",
    "        \n",
    "    def add(self,value):\n",
    "        if(self.root==None):\n",
    "            self.root=TreeNode(value)\n",
    "        else:\n",
    "            self._add(self.root,value)\n",
    "        \n",
    "    def _add(self,root,value):\n",
    "        if(value<=root.data):\n",
    "            if(root.leftChild==None):\n",
    "                root.leftChild=TreeNode(value)\n",
    "            else:\n",
    "                self._add(root.leftChild,value)\n",
    "        else:\n",
    "            if(root.rightChild==None):\n",
    "                root.rightChild=TreeNode(value)\n",
    "            else:\n",
    "                self._add(root.rightChild,value)\n",
    "                \n",
    "    def printTree(self,root):\n",
    "        print root.data\n",
    "        if(root.leftChild!=None):\n",
    "            self.printTree(root.leftChild)\n",
    "        if(root.rightChild!=None):\n",
    "            self.printTree(root.rightChild)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "3\n",
      "2\n",
      "1\n",
      "4\n",
      "7\n",
      "6\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "BST=BinarySearchTree()\n",
    "BST.add(5)\n",
    "BST.add(3)\n",
    "BST.add(2)\n",
    "BST.add(4)\n",
    "BST.add(1)\n",
    "BST.add(7)\n",
    "BST.add(6)\n",
    "BST.add(8)\n",
    "BST.printTree(BST.root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Priority Queues with Binary Heaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The basic operations we will implement for our binary heap are as follows:\n",
    "\n",
    "* BinaryHeap() creates a new, empty, binary heap.\n",
    "* insert(k) adds a new item to the heap.\n",
    "* findMin() returns the item with the minimum key value, leaving item in the heap.\n",
    "* delMin() returns the item with the minimum key value, removing the item from the heap.\n",
    "* isEmpty() returns true if the heap is empty, false otherwise.\n",
    "* size() returns the number of items in the heap.\n",
    "* buildHeap(list) builds a new heap from a list of keys."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "5\n",
      "7\n",
      "11\n"
     ]
    }
   ],
   "source": [
    "from pythonds.trees.binheap import BinHeap\n",
    "\n",
    "bh = BinHeap()\n",
    "bh.insert(5)\n",
    "bh.insert(7)\n",
    "bh.insert(3)\n",
    "bh.insert(11)\n",
    "\n",
    "print(bh.delMin())\n",
    "\n",
    "print(bh.delMin())\n",
    "\n",
    "print(bh.delMin())\n",
    "\n",
    "print(bh.delMin())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(6, 2)\n",
      "([0, (5, 'a'), (7, 'c'), (11, 's'), (3, 'f'), (10, 'g')], 2)\n",
      "([0, (5, 'a'), (3, 'f'), (11, 's'), (7, 'c'), (10, 'g')], 1)\n",
      "([0, (3, 'f'), (5, 'a'), (11, 's'), (7, 'c'), (10, 'g')], 0)\n"
     ]
    }
   ],
   "source": [
    "bh.buildHeap([(5,'a'),(7,'c'),(11,'s'),(3,'f'),(10,'g')])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Heap Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "BinHeap List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/heapOrder.png \\>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "BinHeap insertion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/percUp.png \\>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "delMin:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/percDown.png \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class BinHeap:\n",
    "    def __init__(self):\n",
    "        self.heapList = [0]\n",
    "        self.currentSize = 0\n",
    "    def insert(self,k):\n",
    "        self.heapList.append(k)\n",
    "        self.currentSize = self.currentSize + 1\n",
    "        self.percUp(self.currentSize)\n",
    "    def percUp(self,i):\n",
    "        while i // 2 > 0:\n",
    "            if self.heapList[i] < self.heapList[i // 2]:\n",
    "                tmp = self.heapList[i // 2]\n",
    "                self.heapList[i // 2] = self.heapList[i]\n",
    "                self.heapList[i] = tmp\n",
    "            i = i // 2\n",
    "    def percDown(self,i):\n",
    "        while (i * 2) <= self.currentSize:\n",
    "            mc = self.minChild(i)\n",
    "            if self.heapList[i] > self.heapList[mc]:\n",
    "                tmp = self.heapList[i]\n",
    "                self.heapList[i] = self.heapList[mc]\n",
    "                self.heapList[mc] = tmp\n",
    "            i = mc\n",
    "    def minChild(self,i):\n",
    "        if i * 2 + 1 > self.currentSize:\n",
    "            return i * 2\n",
    "        else:\n",
    "            if self.heapList[i*2] < self.heapList[i*2+1]:\n",
    "                return i * 2\n",
    "            else:\n",
    "                return i * 2 + 1\n",
    "    def delMin(self):\n",
    "        retval = self.heapList[1]\n",
    "        self.heapList[1] = self.heapList[self.currentSize]\n",
    "        self.currentSize = self.currentSize - 1\n",
    "        self.heapList.pop()\n",
    "        self.percDown(1)\n",
    "        return retval\n",
    "    def buildHeap(self,alist):\n",
    "        i = len(alist) // 2\n",
    "        self.currentSize = len(alist)\n",
    "        self.heapList = [0] + alist[:]\n",
    "        while (i > 0):\n",
    "            self.percDown(i)\n",
    "            i = i - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Leetcode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 116. Populating Next Right Pointers in Each Node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary tree\n",
    "\n",
    "    struct TreeLinkNode {\n",
    "      TreeLinkNode *left;\n",
    "      TreeLinkNode *right;\n",
    "      TreeLinkNode *next;\n",
    "    }\n",
    "    \n",
    "Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.\n",
    "\n",
    "Initially, all next pointers are set to NULL.\n",
    "\n",
    "Note:\n",
    "\n",
    "* You may only use constant extra space.\n",
    "* You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).\n",
    "\n",
    "For example,\n",
    "Given the following perfect binary tree,\n",
    "\n",
    "         1\n",
    "       /  \\\n",
    "      2    3\n",
    "     / \\  / \\\n",
    "    4  5  6  7\n",
    "    \n",
    "After calling your function, the tree should look like:\n",
    "\n",
    "         1 -> NULL\n",
    "       /  \\\n",
    "      2 -> 3 -> NULL\n",
    "     / \\  / \\\n",
    "    4->5->6->7 -> NULL\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Since we are only allowed to use constant extra space, a bfs implemented by a queue will not be allowed. It is easy to point a left child to a right child. The recursion should be done as follows:\n",
    "\n",
    "1. Starting from the root, as root.next=None, we only connect the left child to the right child.\n",
    "2. For next layer, as root.left.next is not none, we not only connect the children of left node but also connect root.left.right=root.left.next.left\n",
    "\n",
    "Implementation:\n",
    "\n",
    "1. we use a head to record left most node in each layer\n",
    "2. we use a mover to check if mover.next:\n",
    "\n",
    "mover.left.next=mover.right\n",
    "if mover.next:\n",
    "mover.right.next=mover.next.left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for binary tree with next pointer.\n",
    "# class TreeLinkNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    # @param root, a tree link node\n",
    "    # @return nothing\n",
    "    def connect(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        if root.left:\n",
    "            root.left.next=root.right\n",
    "            mover=root\n",
    "            while mover.next:\n",
    "                mover.right.next=mover.next.left\n",
    "                mover.next.left.next=mover.next.right\n",
    "                mover=mover.next\n",
    "            self.connect(root.left)\n",
    "        else:\n",
    "            return"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It turns out the recursion is redundant, we could avoid recursion as follows:(discussion solution)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def connect(self, root):\n",
    "    while root and root.left:\n",
    "        next = root.left\n",
    "        while root:\n",
    "            root.left.next = root.right\n",
    "            root.right.next = root.next and root.next.left\n",
    "            root = root.next\n",
    "        root = next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=-1 and 3\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 117. Populating Next Right Pointers in Each Node II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Follow up for problem \"Populating Next Right Pointers in Each Node\".\n",
    "\n",
    "What if the given tree could be any binary tree? Would your previous solution still work?\n",
    "\n",
    "Note:\n",
    "\n",
    "* You may only use constant extra space.\n",
    "\n",
    "For example,\n",
    "Given the following binary tree,\n",
    "\n",
    "         1\n",
    "       /  \\\n",
    "      2    3\n",
    "     / \\    \\\n",
    "    4   5    7\n",
    "    \n",
    "After calling your function, the tree should look like:\n",
    "\n",
    "         1 -> NULL\n",
    "       /  \\\n",
    "      2 -> 3 -> NULL\n",
    "     / \\    \\\n",
    "    4-> 5 -> 7 -> NULL\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Given a connected layer, we need to decide in the next layer:\n",
    "\n",
    "1. starting node: \n",
    "\n",
    "while not root.left and not root.right:\n",
    "    root=root.next\n",
    "if root.left:\n",
    "    start=root.left\n",
    "else:\n",
    "    start=root.right\n",
    "\n",
    "2. connection between nodes\n",
    "\n",
    "if root.left and root.right:\n",
    "   root.left.next=root.right\n",
    "prev=start\n",
    "while root.next:\n",
    "     if root.next.left and root.next.right:\n",
    "         prev.next=root.next.left\n",
    "         root.next.left.next=root.next.right\n",
    "         prev=root.next.right\n",
    "     elif root.next.left:\n",
    "         prev.next=root.next.left\n",
    "         prev=root.next.left\n",
    "     else:\n",
    "         prev.next=root.next.right\n",
    "         prev=root.next.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for binary tree with next pointer.\n",
    "# class TreeLinkNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    # @param root, a tree link node\n",
    "    # @return nothing\n",
    "    def connect(self, root):\n",
    "        # pick up the node that has child as starting node for next level\n",
    "        while root and not root.left and not root.right:\n",
    "            root=root.next\n",
    "            \n",
    "        if not root:\n",
    "            return\n",
    "            \n",
    "        # connection between nodes in the next layer\n",
    "        start=None\n",
    "        prev=None\n",
    "        if root.left and root.right:\n",
    "            start=root.left\n",
    "            prev=root.right\n",
    "            root.left.next=root.right\n",
    "        elif root.left:\n",
    "            start=root.left\n",
    "            prev=root.left\n",
    "        else:\n",
    "            start=root.right\n",
    "            prev=root.right\n",
    "            \n",
    "        while root.next:\n",
    "            if root.next.left and root.next.right:\n",
    "                prev.next=root.next.left\n",
    "                root.next.left.next=root.next.right\n",
    "                prev=root.next.right\n",
    "            elif root.next.left:\n",
    "                prev.next=root.next.left\n",
    "                prev=root.next.left\n",
    "            elif root.next.right:\n",
    "                prev.next=root.next.right\n",
    "                prev=root.next.right\n",
    "            \n",
    "            root=root.next\n",
    "            \n",
    "        self.connect(start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Test case 1: perfect balance tree\n",
    "Test case 2:\n",
    "\n",
    "\n",
    "         1 -> NULL\n",
    "       /  \\\n",
    "      2 -> 3 -> NULL\n",
    "     / \\    \\\n",
    "    4-> 5 -> 7 -> NULL\n",
    "\n",
    "Test case 3:\n",
    "\n",
    "\n",
    "         1 -> NULL\n",
    "       /  \\\n",
    "      2 -> 3 -> NULL\n",
    "     / \\    \\\n",
    "    4-> 5 -> 7 -> NULL\n",
    "    /          \\\n",
    "    8 ->        9\n",
    "   \n",
    "Test case 4:\n",
    "\n",
    "\n",
    "         1 -> NULL\n",
    "       /  \\\n",
    "      2 -> 3 -> NULL\n",
    "     / \\    \\\n",
    "    4-> 5 -> 7 -> NULL\n",
    "     \\        \\\n",
    "      8  ->    9"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above code can be improved as follows: bfs level traversal:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def connect(self, node):\n",
    "    tail = dummy = TreeLinkNode(0)\n",
    "    while node:\n",
    "        tail.next = node.left\n",
    "        if tail.next:\n",
    "            tail = tail.next\n",
    "        tail.next = node.right\n",
    "        if tail.next:\n",
    "            tail = tail.next\n",
    "        node = node.next\n",
    "        if not node:\n",
    "            tail = dummy\n",
    "            node = dummy.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above solution, TreeLinkNode(0) is auxiliary\n",
    "         1 -> NULL\n",
    "       /  \\\n",
    "    0->2 -> 3 -> NULL\n",
    "     / \\    \\\n",
    "    4-> 5 -> 7 -> NULL\n",
    "     \\        \\\n",
    "      8  ->    9\n",
    " dummy record the head of next level"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}