"""
 binarytree.py

 An example of a recursive data structure
 (i.e. something that contains other things like itself)
 and recursive functions (i.e. ones that call themselves) 
 to do something to it.

 The recursive stucture here is a binary tree,
 starting from a top and with left and right branches below.

 The small arbitrary one we'll look at here is :

       1
      / \
     2   3
    / \    
   4   5

 The count_nodes and tree_as_string functions 
 both traverse this tree recursively.

 Examples of a tree structures like this include
 family trees and the possible moves in a chess game.

  $ python --version
  python 2.7.12

  $ python binarytree.py
  The top node is <Node name='1' left=2 right=3>.
  Below that is <Node name='2' left=4 right=5> and <Node name='3'>.
  The whole tree is (1 (2 (4) (5)) (3)).
  It has 5 nodes.

 Jim Mahoney | cs.marlboro.edu | Nov 2016 | MIT License
"""

class Node(object):
    """ A node in a binary tree """

    def __init__(self, name='*', left=None, right=None):
        self.name = str(name)
        self.left = left
        self.right = right

    def __str__(self):
        try:
            leftstring = " left={}".format(self.left.name)
        except:
            leftstring = ''
        try:
            rightstring = " right={}".format(self.right.name)
        except:
            rightstring = ''
        return "<Node name='{}'{}{}>".format(
            self.name, leftstring, rightstring)

def make_tree():
    """ Create the tree described at the top of this file,
        and return the root (top) node. """
    five = Node(5)
    four = Node(4)
    three = Node(3)
    two = Node(2, left=four, right=five)
    one = Node(1, left=two, right=three)
    return one

def count_nodes(node):
    """ Return count of nodes at or below this node (recursively). """
    result = 1                                     # count this node as 1 ...
    for child in (node.left, node.right):
        if child != None:                    
            result = result + count_nodes(child)   # ... add add its kids.
    return result

def tree_as_string(node):
    """ Return the entire tree as a string (recursively). """
    result = "(" + node.name
    for child in (node.left, node.right):
        if child != None:
            result = result + " " + tree_as_string(child)
    result = result + ")"
    return result

def main():
    top = make_tree()
    print("The top node is {}.".format(top))
    print("Below that is {} and {}.".format(top.left, top.right))
    print("The whole tree is {}.".format(tree_as_string(top)))
    print("It has {} nodes.".format(count_nodes(top)))

if __name__ == '__main__':
    main()