Binary tree data structure

I am learning about the binary tree data structure and implemented some basic functionality.

It was working great with module level functions until I realized that I need to keep track of the root for operations like checking height. The simplest solution that I could possibly think was of creating a container class to hold the root reference, but all my functions became quite ugly then.

```
class TreeNode(object):
"""Node of a Binary tree."""
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right

def __str__(self):
return "{0}".format(self.key)

class BinaryTree(object):
"""ADT for binary tree."""

def __init__(self, root=None):
self.root = root

def is_root(self, node):
return node.key == self.root.key

def is_leaf(self, node):
"""Checks whether given node is leaf."""
if node is None or self.is_root(node):
return False
return node.left is None and node.right is None

def is_internal(self, node):
"""Checks whether the given node is internal node.

All nodes except leaf nodes are considered internal nodes.
"""
return not self.is_leaf(node)

def is_full(self):
"""Checks if the subtree rooted at the given node is full.

A Binary tree is full when every node other than leaves
has two children.
"""
def recurse(node):
if node is None:
return True
if self.is_leaf(node):
return True
if node.left is not None and node.right is not None:
return recurse(node.left) and recurse(node.right)
return False
return recurse(self.root)

def height(self):
"""Calculates height of the Binary tree."""
return self.node_height(self.root)

def node_height(self, node):
"""Calculates height of the subtree rooted at given node."""
if node is None or self.is_leaf(node):
return 0
return max(self.node_height(node.left), self.node_height(node.right)) + 1

def is_balanced(self):

I see problems in nearly every method.

First of all, PEP 8 specifies four spaces for indentation. Since whitespace is significant in Python, this is a pretty strong convention.

TreeNode.__str__() would be simpler as return str(self.key).

BinaryTree.is_root() returns true if a node happens to contain the same key as the root. That's a very Clintonian interpretation of "is". I would have thought that the straightforward way would be return node is self.root.

In BinaryTree.is_leaf(), I think that node is None and self.is_root(node) are both invalid criteria. If node is None, I don't see how you could call it a leaf node — that's not a node at all. And in the case of a degenerate one-node tree, the root could very well be a leaf as well.

BinaryTree.is_full() would report this tree as being full, which I don't think it is:

A
 / \
B   C
   / \
  D   E

In BinaryTree.node_height(), you treat a leaf node as well as the void below it as being at the same height, which is weird (even if you never use the function that way).

BinaryTree.is_balanced() uses an internal recurse() helper function. Oddly, recurse() isn't recursive. Rather, the node_height() method that it uses is recursive.

I suggest making level_order() into a generator: get rid of res, and instead of res.append(…), you should yield the results.

StackExchange Code Review Q#108459, answer score: 7