""" 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 . Below that is and . 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 "".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()