BST | Python Fiddle

#!/usr/bin/env python

from __future__ import division
from math import log10

class Node(object):
    def __init__(self, value=0,
                 left=None, right=None, 
                 id=None, parent=None):
        self.id = id
        self.left = left
        self.right = right
        self.value = value
        self.parent = parent

def __str__(self):
        if self.left is None and self.right is None:
            return str(self.value)
        else:
            return '%s (%s, %s)' % (
                    str(self.value), 
                    str(self.left), 
                    str(self.right))

def __repr__(self):
        s = 'TreeNode Object (id=' + str(self.id) + \
            ' value='+str(self.value)+')'
        return s

def pretty_print(self):
        # get each levels
        level = [self]
        to_prints = [[self.value]]
        while True:
            is_all_none = True
            next_level = []
            to_print = []
            for n in level:
                if n is None:
                    next_level += [None, None]
                    to_print += ['#','#']
                else:
                    is_all_none = False
                    next_level += [n.left, n.right]
                    left_val = n.left.value if n.left and n.left.value else '#'
                    right_val = n.right.value if n.right and n.right.value else '#'
                    to_print += [left_val, right_val]
            if is_all_none: break
            level = next_level
            to_prints.append(to_print)

#max_val_digits = max([max([len(str(v)) for v in r]) for r in to_prints])
        #print max_val_digits

to_prints = to_prints[:-1] # remove the last row with only '#'
        to_pretty_prints = []
        to_prints.reverse()
        for i, row in enumerate(to_prints):
            row = map(str,row)
            #row = [' '*(max_val_digits-len(v))+v for v in row]
            sep = ' '*(2**(i+1) - 1)
            space = ' '*(2**i - 1)
            to_pretty_prints.insert(0, space + sep.join(row) + space)
        print '\n'.join(to_pretty_prints)

def nodeCount(root):
    if root == None:
        return 0
    return nodeCount(root.left) + nodeCount(root.right) + 1

def leafCount(root):
    if root == None:
        return 0
    if root.left == None and root.right == None:
        return 1
    return leafCount(root.left) + leafCount(root.right)

def leafSum(root):
    if root == None:
        return 0
    if root.left == None and root.right == None:
        return root.value
    return leafSum(root.left) + leafSum(root.right)

def nodeSum(root):
    if root == None:
        return 0
    return nodeSum(root.left) + nodeSum(root.right) + root.value

def hasPathSum(root, no):
    if root == None:
        return False
    # if leaf node evaluate whether the sum of that path is equal to the int provided
    if root.left == None and root.right == None:
        return no == root.value
    # recurse right and left 
    sub_no = no - root.value 
    return hasPathSum(root.left, sub_no) or hasPathSum(root.right, sub_no)

# LCA in a BST
def LCA_bst(root, first, second):
    if root.value > first and root.value > second:
        return LCA_bst(root.left)
    if root.value < first and root.value < first:
        return LCA_bst(root.right)
    return root

def getHeight(root):
    if root == None:
        return 0
    left = getHeight(root.left) 
    right = getHeight(root.right) 
    if left == -1 or right == -1:
        return -1
    if abs(left - right) > 1:
        return -1
    return max(left, right) + 1

# check if a tree is balanced or not 
def balanced(root):
    if getHeight(root) == -1:
        return False
    else:
        return True

# given a list of sorted integers, create a BST
def createBST(l):
    if len(l) < 1:
        return None
    midIndex = len(l)//2
    print str(midIndex) + ", " + str(l[midIndex])
    root = Node(l[midIndex])
    root.left = createBST(l[:midIndex])
    root.right = createBST(l[midIndex + 1:])
    return root

def invertTree(root):
    if root == None:
        return root
    temp = root.left
    root.left = invertTree(root.right)
    root.right = invertTree(temp)
    return root

root = Node(value=5,
            left=Node(value=4,
                 left=Node(value=1,
                      right=Node(value=2))
            ),
            right=Node(value=8,
                 left=Node(value=3),
                 right=Node(value=4,
                    left=Node(value=9),
                    right=Node(value=1))
            )
        )

BST = Node(value=5,
            left=Node(value=2,
                 left=Node(value=1,
                    right=Node(value=1.5, 
                        left=Node(value=1.2))),
                 right=Node(value=3)
            ),
            right=Node(value=9,
                 left=Node(value=7),
                 right=Node(value=15,
                    right=Node(value=16)
                 )
            )
        )

BST2 = Node(value=5,
            left=Node(value=2,
                 left=Node(value=1,
                    right=Node(value=1.5, 
                        )),
                 right=Node(value=3)
            ),
            right=Node(value=9,
                 left=Node(value=7),
                 right=Node(value=15,
                    right=Node(value=16)
                 )
            )
        )

if __name__ == '__main__':
    root.pretty_print()
    print
    BST.pretty_print()
    print
    BST2.pretty_print()
    print
    
    BST3 = createBST([0,1,2,3,4,5,6])
    BST3.pretty_print()
    
    BST4 = invertTree(BST3)
    BST4.pretty_print()
    
    
    print balanced(BST)
    print balanced(BST2)
    print "LCA is: %s " % LCA_bst(BST,1.2,7 )

print 
    print "Has Path Sum: %s" % hasPathSum(root, 16)
    print "node count: %s" % nodeCount(root)
    print "leaf count: %s" % leafCount(root)
    print "leaf sum: %s" % leafSum(root)
    print "node sum: %s" % nodeSum(root)
    print
    print nodeCount(BST)
    print leafCount(BST)
    print leafSum(BST)
    print nodeSum(BST)

Python Fiddle

Python Cloud IDE