{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,label,left,right):\n",
    "        self.label = label\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "   \n",
    "    def __repr__(self):\n",
    "        left = 'None' if self.left is None  else self.left.label\n",
    "        right = 'None' if self.right is None else self.right.label\n",
    "    \n",
    "        return \"Node: (label={0},left_node_label={1},right_node_label={2})\".format(self.label,left,right)    \n",
    "    \n",
    "    \n",
    "    def search_children(self,target_label):\n",
    "        if self.label == target_label:\n",
    "            return (True,self)\n",
    "        else:\n",
    "            if self.left is None and self.right is None:\n",
    "                return (False,None)\n",
    "            \n",
    "            if self.left is not None:\n",
    "                return self.left.search_children(target_label)   \n",
    "               \n",
    "            if self.right is not None:\n",
    "                return self.right.search_children(target_label)\n",
    "          \n",
    "                    \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#        a\n",
    "#       / \\\n",
    "#      /   \\\n",
    "#     b    c\n",
    "#    / \\  / \\\n",
    "#   d  e b'  f\n",
    "#  /\n",
    "# c'\n",
    "\n",
    "# I've created two nodes with labels 'b' and 'c' so that we can\n",
    "# test whether we are indeed searching depth-first\n",
    "b_prime = Node('b',None,None)\n",
    "c_prime = Node('c',None,None)\n",
    "f = Node('f',None,None)\n",
    "e = Node('e',None,None)\n",
    "d = Node('d',c_prime,None)\n",
    "c = Node('c',b_prime,f)\n",
    "b = Node('b',d,e)\n",
    "a = Node('a',b,c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# simple depth-first search in a binary tree\n",
    "# a tree has no cycles!\n",
    "def depth_first_search(root_node, target_label):\n",
    "    return root_node.search_children(target_label)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, Node: (label=a,left_node_label=b,right_node_label=c))"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "depth_first_search(a,'a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, Node: (label=d,left_node_label=c,right_node_label=None))"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "depth_first_search(a,'d')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, Node: (label=b,left_node_label=d,right_node_label=e))"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# the node with label 'b' on the left subtree will be found first,\n",
    "# because this is a depth first search\n",
    "depth_first_search(a,'b')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, None)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# this label was not found\n",
    "depth_first_search(a,'j')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, Node: (label=c,left_node_label=None,right_node_label=None))"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# the node with label 'c' on the left subtree will be found first,\n",
    "# because this is a depth first search\n",
    "depth_first_search(a,'c')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}