{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "This notebook was prepared by [Donne Martin](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solution Notebook" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem: Determine the height of a tree.\n", "\n", "* [Constraints](#Constraints)\n", "* [Test Cases](#Test-Cases)\n", "* [Algorithm](#Algorithm)\n", "* [Code](#Code)\n", "* [Unit Test](#Unit-Test)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Constraints\n", "\n", "* Is this a binary tree?\n", " * Yes\n", "* Can we assume we already have a Node class with an insert method?\n", " * Yes\n", "* Can we assume this fits memory?\n", " * Yes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Test Cases\n", "\n", "* 5 -> 1\n", "* 5, 2, 8, 1, 3 -> 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm\n", "\n", "We'll use a recursive algorithm.\n", "\n", "* If the current node is None, return 0\n", "* Else, return 1 + the maximum height of the left or right children\n", " \n", "Complexity:\n", "* Time: O(n)\n", "* Space: O(h), where h is the height of the tree" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Code" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "%run ../bst/bst.py" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "class BstHeight(Bst):\n", "\n", " def height(self, node):\n", " if node is None:\n", " return 0\n", " return 1 + max(self.height(node.left),\n", " self.height(node.right))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Unit Test" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Overwriting test_height.py\n" ] } ], "source": [ "%%writefile test_height.py\n", "import unittest\n", "\n", "\n", "class TestHeight(unittest.TestCase):\n", "\n", " def test_height(self):\n", " bst = BstHeight(Node(5))\n", " self.assertEqual(bst.height(bst.root), 1)\n", " bst.insert(2)\n", " bst.insert(8)\n", " bst.insert(1)\n", " bst.insert(3)\n", " self.assertEqual(bst.height(bst.root), 3)\n", "\n", " print('Success: test_height')\n", "\n", "\n", "def main():\n", " test = TestHeight()\n", " test.test_height()\n", "\n", "\n", "if __name__ == '__main__':\n", " main()" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Success: test_height\n" ] } ], "source": [ "%run -i test_height.py" ] } ], "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.2" } }, "nbformat": 4, "nbformat_minor": 1 }