Binary tree data structure

Question

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):
 """Checks whether the subtree rooted at the given node is balanced.
 The subtree rooted at node is balanced if the difference between the
 height of the left left subtree and right subtree is within [-1, 0, 1].
 """
 def recurse(node):
 if node is None:
 return True
 lheight = self.node_height(node.left)
 rheight = self.node_height(node.right)
 return abs(lheight - rheight) < 1
 return recurse(self.root)
 @classmethod
 def level_order(cls, node):
 """Given Binary Tree node gives list of nodes in each level."""
 if node is None:
 return
 current_level = [node]
 res = []
 while current_level:
 res.append(current_level)
 next_level = []
 for node in current_level:
 if node.left:
 next_level.append(node.left)
 if node.right:
 next_level.append(node.right)
 current_level = next_level
 return res
 @classmethod
 def build_tree(cls, inorder, preorder):
 """Builds a Binary Tree from given inorder and preorder traversal.
 Steps:
 1. Take the first element from the preorder list.
 2. Get the index of the element from inorder list.
 3. Set the element as root.
 4. Take all elements left to root from inorder list.
 5. Take all elements right to root from inorder list.
 6. Calculate preorder list for left and right subtree respectively.
 7. Repeat from step 1 for each subtree.
 """
 def insert_left(parent, node):
 parent.left = node
 return parent
 def insert_right(parent, node):
 parent.right = node
 return parent
 def recurse(node, inorder, preorder):
 if len(preorder) == 1:
 return TreeNode(preorder)
 key = preorder[0]
 root_index = inorder.find(key)
 inorder_left = inorder[:root_index]
 inorder_right = inorder[root_index+1:]
 preorder_left = preorder[1:len(inorder_left)+1]
 preorder_right = preorder[root_index+1:]
 node = TreeNode(key)
 if len(inorder_left):
 insert_left(node, recurse(None, inorder_left, preorder_left))
 if len(inorder_right):
 insert_right(node, recurse(None, inorder_right, preorder_right))
 return node
 node = recurse(None, inorder, preorder)
 return cls(node)
 def print_tree(self, node):
 node = self.root if node is None else node
 for level in self.level_order(root):
 for node in level:
 print node,
 print
import unittest
class TestBinaryTree(unittest.TestCase):
 #@unittest.skip("demonstrating skipping")
 def test_inorder(self):
 bt = BinaryTree.build_tree('DBEAFIC', 'ABDEICF')
 expected = [['A'], ['B', 'I'], ['D', 'E', 'C', 'F']]
 actual = []
 for level in bt.level_order(bt.root):
 actual.append([node.key for node in level ])
 self.assertEqual(actual, expected)
 def test_isFull(self):
 bt = BinaryTree.build_tree('DBEAFIC', 'ABDEICF')
 self.assertTrue(bt.is_full())
 bt = BinaryTree.build_tree('DBEAFC', 'ABDECF')
 self.assertFalse(bt.is_full())
class TestBinaryTreeHeight(unittest.TestCase):
 def test_none(self):
 bt = BinaryTree()
 self.assertEqual(bt.height(), 0)
 def test_only_root(self):
 bt = BinaryTree.build_tree('A', 'A')
 self.assertEqual(bt.height(), 1)
 def test_tree(self):
 bt = BinaryTree.build_tree('DBEAFC', 'ABDECF')
 self.assertEqual(bt.height(), 2)
class TestBinaryTreeBalance(unittest.TestCase):
 def test_leftSkewed(self):
 """
 A
 /
 B
 /
 C
 """
 bt = BinaryTree.build_tree('CBA', 'ABC')
 self.assertFalse(bt.is_balanced())
 def test_rightSkewed(self):
 """
 A
 \
 B
 \
 C
 """
 bt = BinaryTree.build_tree('ABC', 'ABC')
 self.assertFalse(bt.is_balanced())
 def test_balanced(self):
 """
 A
 / \
 B C
 / \
 D E
 """
 bt = BinaryTree.build_tree('DBEAC', 'ABDEC')
 self.assertFalse(bt.is_balanced())
 def test_unbalanced(self):
 """
 A
 / \
 B C
 / \
 D E
 / \
 F G
 """
 bt = BinaryTree.build_tree('DBFEGAC', 'ABDEFGC')
 self.assertFalse(bt.is_balanced())
if __name__ == '__main__':
 unittest.main()

Note

Some comments in the methods may seem arbitrary because initially they were module level functions which expected any node.

Doubts

1. What strategy I could have adopted to keep my code clean?
2. I didn't store a height for each node to keep my objects lean. Instead, in is_balanced, I am calculating expensive calculations. Is this fine?
3. [TODO].

Answer 1

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.

• CodeYogi: Regarding degenerated tree yes, that is the main confusion for me. Given only single node, what would you call it? root or leaf? and therefor I had to make a container class that just holds the root reference, again I was not sure to check root via object reference equality or via its key? later choice doesn't allow me to have duplicate key in the Binary tree, I am not sure if duplicates keys are allowed in Standard implementation.
• CodeYogi: Also, can I have is_bst as part of the API here? actually I am learning while doing things hence I have started from scratch and want to see how things matter, instead of reading some standard book line by line.
• 200_success: Just go by the definition: a leaf node has no children. A root node might also be a leaf node.
• 200_success: Offering an is_bst() method would be a bit weird, since there is no support for binary search here.
• holroy: @200_success, as I understand it is_full is correct, but it does check for a full tree (no single childs), not a complete tree (full leaf nodes at same level, and single/empty leaf to the right)

Answer 2

First of all, I don't know python, so my answer will be pretty generic.

That being said, let's address your doubts:

1. I'd suggest doing the implementation of the various methods in the TreeNode class. In this way, from the BinaryTree you just have to call root.doStuff.
2. It's fine as long as you call the method very few times and space is critical. Otherwise I'd suggest to keep in each node a balance factor (like in AVL trees for example).

Let me know if anything's unclear.

• CodeYogi: Then in that case it will be AVL Tree, right? :)
• Gentian Kasa: @CodeYogi, unless you rebalance the tree each time the tree loses balance, like when you insert a new element or remove an existing one, (as AVL Trees do) it will remain a Binary Tree :)
• CodeYogi: If that's the case then its good that I am done with Binary Tree and can move to AVL Tree now :)
• Gentian Kasa: For what I see in the code (if I understood correctly) you implemented a regular Binary Tree. AVL Trees are binary trees used for searching purposes, so I'd say it's better to move to Binary Search Trees before moving to AVL Trees, but that's just my opinion on the matter.
• CodeYogi: Cool! and that was what I was thinking right now. See my comments on @200_success answer above :)