# 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):

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

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.

• 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. Oct 23 '15 at 8:15
• 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. Oct 23 '15 at 8:17
• Just go by the definition: a leaf node has no children. A root node might also be a leaf node. Oct 23 '15 at 8:19
• Offering an is_bst() method would be a bit weird, since there is no support for binary search here. Oct 23 '15 at 8:20
• @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) Oct 23 '15 at 9:29

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

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.
• Then in that case it will be AVL Tree, right? :) Oct 23 '15 at 8:00
• @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 :) Oct 23 '15 at 8:03
• If that's the case then its good that I am done with Binary Tree and can move to AVL Tree now :) Oct 23 '15 at 8:07
• 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. Oct 23 '15 at 8:27