Reader Execise: Binary Tree Traversal with Generator Function

BinaryTreeTraversal.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "BinaryTreeTraversal.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/abhabongse/30c60a12c47ebb9fac4ccc605714aa76/BinaryTreeTraversal.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_J8zRwfoncuo",
        "colab_type": "text"
      },
      "source": [
        "# **Exercise:** Binary Tree Traversal\n",
        "Implement different kinds of tree node traversals.  \n",
        "[Read more information about each kind of traversal here.](https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search_of_binary_tree)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-Flj-vMMnncD",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from dataclasses import dataclass\n",
        "from typing import Any, Optional, Iterator\n",
        "\n",
        "@dataclass\n",
        "class BinaryTree:\n",
        "    \"\"\"\n",
        "    Implementation of binary tree with 3 kinds of tree node traversals:\n",
        "    pre-order traversal, in-order traversal, and post-order traversal.\n",
        "    \"\"\"\n",
        "    value: Any\n",
        "    left: Optional['BinaryTree']\n",
        "    right: Optional['BinaryTree']\n",
        "\n",
        "    def preorder_traverse(self) -> Iterator[Any]:\n",
        "        \"\"\"\n",
        "        An iterator which yields a sequence of node values\n",
        "        in pre-order traversal.\n",
        "        \"\"\"\n",
        "        # TODO: implement this\n",
        "        ...\n",
        "\n",
        "    def inorder_traverse(self) -> Iterator[Any]:\n",
        "        \"\"\"\n",
        "        An iterator which yields a sequence of node values\n",
        "        in in-order traversal.\n",
        "        \"\"\"\n",
        "        # TODO: implement this\n",
        "        ...\n",
        "\n",
        "    def postorder_traverse(self) -> Iterator[Any]:\n",
        "        \"\"\"\n",
        "        An iterator which yields a sequence of node values\n",
        "        in post-order traversal.\n",
        "        \"\"\"\n",
        "        # TODO: implement this\n",
        "        ..."
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BpYhzq4uplru",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "sample_tree = BinaryTree(\n",
        "    23, \n",
        "    BinaryTree(\n",
        "        17, \n",
        "        BinaryTree(6, None, None), \n",
        "        BinaryTree(\n",
        "            20, \n",
        "            BinaryTree(19, None, None), \n",
        "            BinaryTree(\n",
        "                22, \n",
        "                BinaryTree(21, None, None), \n",
        "                None,\n",
        "            ),\n",
        "        ),\n",
        "    ),\n",
        "    BinaryTree(\n",
        "        40,\n",
        "        BinaryTree(32, None, None),\n",
        "        None,\n",
        "    ),\n",
        ")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fdrNEnEwc0TK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Ensure that the generator functions are implemented\n",
        "import inspect\n",
        "\n",
        "assert inspect.isgeneratorfunction(sample_tree.preorder_traverse)\n",
        "assert inspect.isgeneratorfunction(sample_tree.inorder_traverse)\n",
        "assert inspect.isgeneratorfunction(sample_tree.postorder_traverse)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dffWKKURc0Wf",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Correctness check\n",
        "assert list(sample_tree.preorder_traverse()) == [23, 17, 6, 20, 19, 22, 21, 40, 32]\n",
        "assert list(sample_tree.inorder_traverse()) == [6, 17, 19, 20, 21, 22, 23, 32, 40]\n",
        "assert list(sample_tree.postorder_traverse()) == [6, 19, 21, 22, 20, 17, 32, 40, 23]"
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}