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).

Solution Notebook

Problem: Determine the height of a tree.

Constraints
Test Cases
Algorithm
Code
Unit Test

Constraints

Is this a binary tree?
- Yes
Can we assume we already have a Node class with an insert method?
- Yes

Test Cases

5 -> 1
5, 2, 8, 1, 3 -> 3

Algorithm

We'll use a recursive algorithm.

If the current node is None, return 0
Else, return 1 + the maximum height of the left or right children

Complexity:

Time: O(n)
Space: O(h), where h is the height of the tree

Code



In [1]:

    
%run ../bst/bst.py



In [2]:

    
%%writefile height.py
def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), 
                   height(node.right))









    



Writing height.py



In [3]:

    
%run height.py

Unit Test



In [4]:

    
%%writefile test_height.py
from nose.tools import assert_equal


class TestHeight(object):

    def test_height(self):
        root = Node(5)
        assert_equal(height(root), 1)
        insert(root, 2)
        insert(root, 8)
        insert(root, 1)
        insert(root, 3)
        assert_equal(height(root), 3)

        print('Success: test_height')


def main():
    test = TestHeight()
    test.test_height()


if __name__ == '__main__':
    main()









    



Overwriting test_height.py



In [5]:

    
%run -i test_height.py









    



Success: test_height