Trees and Tree Algorithms

Binary Heap

A complete binary tree is a tree in which each level has all of its nodes.

To find the parent of any node in the tree, we can simply use Python’s integer division. Given that a node is at position $n$ in the list, the parent is at position $𝑛//2$.

A Complete Binary Tree along with its List Representation

The Heap Order Property

In a heap, for every node $𝑥$ with parent $𝑝$, the key in $𝑝$ is smaller than or equal to the key in $𝑥$.

Binary Tree Applications

Parse trees can be used to represent real-world constructions like sentences or mathematical expressions.

A Parse Tree for a Simple Sentence

Tree Traversals

preorder: In a preorder traversal, we visit the root node first, then recursively do a preorder traversal of the left subtree, followed by a recursive preorder traversal of the right subtree.

inorder: In an inorder traversal, we recursively do an inorder traversal on the left subtree, visit the root node, and finally do a recursive inorder traversal of the right subtree.

postorder: In a postorder traversal, we recursively do a postorder traversal of the left subtree and the right subtree followed by a visit to the root node.

Representing a Book as a Tree

Suppose that you wanted to read this book from front to back. The preorder traversal gives you exactly that ordering. Starting at the root of the tree (the Book node) we will follow the preorder traversal instructions. We recursively call preorder on the left child, in this case Chapter 1. We again recursively call preorder on the left child to get to Section 1.1. Since Section 1.1 has no children, we do not make any additional recursive calls. When we are finished with Section 1.1, we move up the tree to Chapter 1.

# function
def preorder(tree): 
    if tree: 
        print(tree.get_root_val()) 
        preorder(tree.get_left_child()) 
        preorder(tree.get_right_child())

# method
def preorder(self): 
    print(self.key) 
    if self.left_child: 
        self.left.preorder() 
    if self.right_child: 
        self.right.preorder()

# function
def postorder(tree): 
    if tree != None: 
        postorder(tree.get_left_child()) 
        postorder(tree.get_right_child()) 
        print(tree.get_root_val())

# function
def inorder(tree): 
    if tree != None: 
        inorder(tree.get_left_child()) 
        print(tree.get_root_val()) 
        inorder(tree.get_right_child())

Binary Tree and its traversal using python.

Binary tree are the tree where one node can have only two child and cannot have more than two. Traversal means visiting all the nodes of the Binary tree. There are three types of traversal.

Lets take the below tree for example.

Binary Tree and its traversal using python.

Inorder traversal

In order traversal means visiting first left, then root and then right.

So the traversal of above tree would be 4 2 5 1 3

Pre Order Traversal

In this traversal we first visit root, then left, then right

It will be something like this 1 2 4 5 3

Post Order traversal

Here we first visit left, then right and then root.

It will be something like this 4 5 2 3 1

These were the traversal now lets code it in python

class Node:
   def __init__(self,data):
       self.left = None
       self.right = None
       self.data = data

def inOrder(root):
   if root:
       inOrder(root.left)
       print (root.data)
       inOrder(root.right)

def preOrder(root):
   if root:
       print (root.data)
       preOrder(root.left)
       preOrder(root.right)

def postOrder(root):
   if root:
       postOrder(root.left)
       postOrder(root.right)
       print (root.data)

#making the tree 
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print inOrder(root)
#4 2 5 1 3
print preOrder(root)
#1 2 4 5 3
print postOrder(root)
#4 5 2 3 1

So this is how you write the binary tree in Python.

Lets have a look at the script.

We made a class Node which represent the node of Binary tree. We initialize the node with data and left and right child as None.

When we add new child we simple use root.left or root.left.left to add a new child.

Now lets have a look at the traversal functions.

In all these functions we took advantage of recursion and passed the subtrees in the functions again to print in proper order. In Inorder function, we first pass the left subtree to Inorder then print the node and then pass the right subtree. Thus made left, root and right. Similarly we did for the other two.

Here we took a look into how to code binary Tree and its traversal using python.

Algorithms: Mirror a Binary tree using python

Binary tree are the tree where one node can have only two child and cannot have more than two. Traversal means visiting all the nodes of the Binary tree.

Lets take the below tree for example.

Algorithms: Mirror a Binary tree using python

So we will be writing python code for changing the tree to its mirror.

class Node:
   def __init__(self,data):
       self.left = None
       self.right = None
       self.data = data

def inOrder(root):
   if root:
       inOrder(root.left)
       print (root.data)
       inOrder(root.right)

def mirror(root):
    if root:
        mirror(root.left)
        mirror(root.right)
        root.left, root.right = root.right, root.left


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.right.left = Node(5)

print inOrder(root)
# 4 2 1 5 3
print '\n'
mirror(root)
print inOrder(root)
# 5 3 1 4 2

Thus you can see the mirror trees inorder traversal. It was really simple we just traversed the tree and changed the right subtree with left and left subtree with right subtree.

Level order traversal of a binary tree.

Level order traversal means that we visit the nodes level by level. Like for below tree the level order traversal will be

Level order traversal of a binary tree.

Its Level order traversal will be

1 2 3 4 5

Here is the code for doing that.

class Node:

        def __init__(self,data):
                self.left = None
                self.right = None
                self.data = data

def level_order(queue):

        if len(queue) == 0:
                return

        node = queue[0]
        queue.pop(0)
        
        if node.left:
                queue.append(node.left)

        if node.right:
                queue.append(node.right)

        print node.data
        level_order(queue)

queue = list()
root = Node(1)

queue.append(root)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
level__order(queue)

# 1 2 3 4 5 

Algorithms: Binary Search Tree and its functionality in python

Back in the algorithms section with python we are going to see how we can code Binary Search Tree and its functionality in python. Binary search tree are binary tree where the left child is less than root and right child is greater than root. We will be performing insertion, searching, traversal, min and other functions. Read more about them here.Level order traversal of a binary tree.

Level order traversal of a binary tree.

Binary Search Tree and its functionality in python

Lets look at the code below.

class Node():
   def __init__(self,data):
      self.left = None
      self.right = None
      self.data = data


def insert(root, data):
   if root.data > data:
       if root.left:
           insert(root.left,data)
       else:
           tmp = Node(data)
           root.left = tmp
       elif root.data < data:
           if root.right:
               insert(root.right,data)
           else:
               tmp = Node(data)
               root.right = tmp
       else:
           print "Key already exist"


def in_order(root):
   if root:
       in_order(root.left)
       print root.data,
       in_order(root.right)


def search(root,key):
    if root:
        if root.data == key:
            return True
        elif root.data < key:
            return search(root.right, key)
        else:
            return search(root.left, key)
    return False 


def get_min(root):
   while root.left:
       root = root.left
   return root.data


def get_max(root):
   while root.right:
       root = root.right
   return root.data


a = Node(4)
insert(a,2)
insert(a,5)
insert(a,1)
insert(a,3)
insert(a,8)
in_order(a)


print search(a,8)
print search(a,2)
print search(a,23)
print get_max(a)
print get_min(a)

What we did here:

Node class to make the nodes of binary search tree.

Then insert functions, what this function is doing is checking if the data is lesser than node then moves to left child else moves to right child and place it at the end.

Search function again works same as insert functions. The only difference is in this we are getting and telling if the data is present while in insert we are adding node to the true.

In order traversal to visit all the node. Do you know in order traversal of binary search tree is in sorted order.

Get min and Get max functions to get the minimum and maximum of the Binary Search Tree.

Delete I am leaving delete function for you. If you are stuck comment below and I will write a delete function for you.

Rosettacode.org

Procedural

from collections import namedtuple
from sys import stdout
 
Node = namedtuple('Node', 'data, left, right')
tree = Node(1,
            Node(2,
                 Node(4,
                      Node(7, None, None),
                      None),
                 Node(5, None, None)),
            Node(3,
                 Node(6,
                      Node(8, None, None),
                      Node(9, None, None)),
                 None))
 
def printwithspace(i):
    stdout.write("%i " % i)
 
def preorder(node, visitor = printwithspace):
    if node is not None:
        visitor(node.data)
        preorder(node.left, visitor)
        preorder(node.right, visitor)
 
def inorder(node, visitor = printwithspace):
    if node is not None:
        inorder(node.left, visitor)
        visitor(node.data)
        inorder(node.right, visitor)
 
def postorder(node, visitor = printwithspace):
    if node is not None:
        postorder(node.left, visitor)
        postorder(node.right, visitor)
        visitor(node.data)
 
def levelorder(node, more=None, visitor = printwithspace):
    if node is not None:
        if more is None:
            more = []
        more += [node.left, node.right]
        visitor(node.data)
    if more:    
        levelorder(more[0], more[1:], visitor)
 
stdout.write('  preorder: ')
preorder(tree)
stdout.write('\n   inorder: ')
inorder(tree)
stdout.write('\n postorder: ')
postorder(tree)
stdout.write('\nlevelorder: ')
levelorder(tree)
stdout.write('\n')

Sample output:

  preorder: 1 2 4 7 5 3 6 8 9 
   inorder: 7 4 2 5 1 8 6 9 3 
 postorder: 7 4 5 2 8 9 6 3 1 
levelorder: 1 2 3 4 5 6 7 8 9 

Class based

Subclasses a namedtuple adding traversal methods that apply a visitor function to data at nodes of the tree in order

from collections import namedtuple
from sys import stdout
 
class Node(namedtuple('Node', 'data, left, right')):
    __slots__ = ()
 
    def preorder(self, visitor):
        if self is not None:
            visitor(self.data)
            Node.preorder(self.left, visitor)
            Node.preorder(self.right, visitor)
 
    def inorder(self, visitor):
        if self is not None:
            Node.inorder(self.left, visitor)
            visitor(self.data)
            Node.inorder(self.right, visitor)
 
    def postorder(self, visitor):
        if self is not None:
            Node.postorder(self.left, visitor)
            Node.postorder(self.right, visitor)
            visitor(self.data)
 
    def levelorder(self, visitor, more=None):
        if self is not None:
            if more is None:
                more = []
            more += [self.left, self.right]
            visitor(self.data)
        if more:    
            Node.levelorder(more[0], visitor, more[1:])
 
 
def printwithspace(i):
    stdout.write("%i " % i)
 
 
tree = Node(1,
            Node(2,
                 Node(4,
                      Node(7, None, None),
                      None),
                 Node(5, None, None)),
            Node(3,
                 Node(6,
                      Node(8, None, None),
                      Node(9, None, None)),
                 None))
 
 
if __name__ == '__main__':
    stdout.write('  preorder: ')
    tree.preorder(printwithspace)
    stdout.write('\n   inorder: ')
    tree.inorder(printwithspace)
    stdout.write('\n postorder: ')
    tree.postorder(printwithspace)
    stdout.write('\nlevelorder: ')
    tree.levelorder(printwithspace)
    stdout.write('\n')

Output:

As above.

Python: Composition of pure (curried) functions

Currying by default is probably not particularly 'Pythonic', but it does work well with higher-order functions – giving us more flexibility in compositional structure. It also often protects us from over-proliferation of the slightly noisy lambda keyword. (See for example the use of the curried version of map in the code below).

The approach taken here is to focus on the evaluation of expressions, rather than the sequencing of procedures. To keep evaluation simple and easily rearranged, mutation is stripped back wherever possible, and 'pure' functions, with inputs and outputs but, ideally, with no side-effects (and no sensitivities to global variables) are the basic building-block.

Composing pure functions also works well with library-building and code reuse – the literature on functional programming (particularly in the ML / OCaml / Haskell tradition) is rich in reusable abstractions for our toolkit. Some of them have already been absorbed, with standard or adjusted names, into the Python itertools module. (See the itertools module preface, and the takewhile function below).

Here, for example, for the pre-, in- and post- orders, we can define a very general and reusable foldTree (a catamorphism over trees rather than lists) and just pass 3 different (rather simple) sequencing functions to it.

This level of abstraction and reuse brings real efficiencies – the short and easily-written foldTree, for example, doesn't just traverse and list contents in flexible orders - we can pass all kinds of things to it. For the sum of all the numbers in the tree, we could write:

foldTree(lambda x: lambda xs: x + sum(xs))(tree)

and for various other metrics, and the traversal sequences:

Works with: Python version 3

'''Tree traversals'''
 
from itertools import (chain, takewhile)
from functools import (reduce)
from operator import (mul)
 
 
# foldTree :: (a -> [b] -> b) -> Tree a -> b
def foldTree(f):
    '''The catamorphism on trees.
       A summary value derived by a depth-first fold.'''
    def go(node):
        return f(root(node))(
            list(map(go, nest(node)))
        )
    return lambda tree: go(tree)
 
 
# levels :: Tree a -> [[a]]
def levels(tree):
    '''A list of the nodes at each level of the tree.'''
    map_ = curry(map)
    return list(
        map_(map_(root))(
            takewhile(
                bool,
                iterate(concatMap(nest))(
                    [tree]
                )
            )
        )
    )
 
 
# preorder :: a -> [[a]] -> [a]
def preorder(x):
    '''This node followed by the rest.'''
    return lambda xs: [x] + concat(xs)
 
 
# inorder :: a -> [[a]] -> [a]
def inorder(x):
    '''Descendants of any first child,
       then this node, then the rest.'''
    return lambda xs: (
        xs[0] + [x] + concat(xs[1:]) if xs else [x]
    )
 
 
# postorder :: a -> [[a]] -> [a]
def postorder(x):
    '''Descendants first, then this node.'''
    return lambda xs: concat(xs) + [x]
 
 
# levelorder :: Tree a -> [a]
def levelorder(tree):
    '''Top-down concatenation of this node
       with the rows below.'''
    return concat(levels(tree))
 
 
# treeSum :: Tree Int -> Int
def treeSum(x):
    '''This node's value + the sum of its descendants.'''
    return lambda xs: x + sum(xs)
 
 
# treeSum :: Tree Int -> Int
def treeProduct(x):
    '''This node's value * the product of its descendants.'''
    return lambda xs: x * numericProduct(xs)
 
 
# treeMax :: Tree Int -> Int
def treeMax(x):
    '''Maximum value of this node and any descendants.'''
    return lambda xs: max([x] + xs)
 
 
# treeMin :: Tree Int -> Int
def treeMin(x):
    '''Minimum value of this node and any descendants.'''
    return lambda xs: min([x] + xs)
 
 
# nodeCount :: Tree a -> Int
def nodeCount(_):
    '''One more than the total number of descendants.'''
    return lambda xs: 1 + sum(xs)
 
 
# treeWidth :: Tree a -> Int
def treeWidth(_):
    '''Sum of widths of any children, or a minimum of 1.'''
    return lambda xs: sum(xs) if xs else 1
 
 
# treeDepth :: Tree a -> Int
def treeDepth(_):
    '''One more than that of the deepest child.'''
    return lambda xs: 1 + (max(xs) if xs else 0)
 
 
# TEST ----------------------------------------------------
# main :: IO ()
def main():
    '''Test'''
 
    # tree :: Tree Int
    tree = Node(1)([
        Node(2)([
            Node(4)([
                Node(7)([])
            ]),
            Node(5)([])
        ]),
        Node(3)([
            Node(6)([
                Node(8)([]),
                Node(9)([])
            ])
        ])
    ])
 
    for f in [preorder, inorder, postorder, levelorder,
              treeSum, treeProduct, treeMin, treeMax,
              nodeCount, treeWidth, treeDepth]:
        s = f.__name__
        print(
            s.rjust(12, ' ') + ':',
            (foldTree(f) if 'levelorder' != s else f)(
                tree
            )
        )
 
 
# GENERIC -------------------------------------------------
 
 
# Node :: a -> [Tree a] -> Tree a
def Node(v):
    '''Contructor for a Tree node which connects a
       value of some kind to a list of zero or
       more child trees.'''
    return lambda xs: {'type': 'Node', 'root': v, 'nest': xs}
 
 
# nest :: Tree a -> [Tree a]
def nest(tree):
    '''Accessor function for children of tree node'''
    return tree['nest'] if 'nest' in tree else None
 
 
# root :: Dict -> a
def root(tree):
    '''Accessor function for data of tree node'''
    return tree['root'] if 'root' in tree else None
 
 
# concat :: [[a]] -> [a]
# concat :: [String] -> String
def concat(xxs):
    '''The concatenation of all the elements in a list.'''
    xs = list(chain.from_iterable(xxs))
    unit = '' if isinstance(xs, str) else []
    return unit if not xs else (
        ''.join(xs) if isinstance(xs[0], str) else xs
    )
 
 
# concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
    '''Concatenated list over which a function has been mapped.
       The list monad can be derived by using a function f which
       wraps its output a in list,
       (using an empty list to represent computational failure).'''
    return lambda xs: list(
        chain.from_iterable(
            map(f, xs)
        )
    )
 
 
# curry :: ((a, b) -> c) -> a -> b -> c
def curry(f):
    '''A curried function derived
       from an uncurried function.'''
    return lambda a: lambda b: f(a, b)
 
 
# iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
    '''An infinite list of repeated applications of f to x.'''
    def go(x):
        v = x
        while True:
            yield v
            v = f(v)
    return lambda x: go(x)
 
 
# numericProduct :: [Num] -> Num
def numericProduct(xs):
    '''The arithmetic product of all numbers in xs.'''
    return reduce(mul, xs, 1)
 
 
if __name__ == '__main__':
    main()

Output:

    preorder: [1, 2, 4, 7, 5, 3, 6, 8, 9]
     inorder: [7, 4, 2, 5, 1, 8, 6, 9, 3]
   postorder: [7, 4, 5, 2, 8, 9, 6, 3, 1]
  levelorder: [1, 2, 3, 4, 5, 6, 7, 8, 9]
     treeSum: 45
 treeProduct: 362880
     treeMin: 1
     treeMax: 9
   nodeCount: 9
   treeWidth: 4
   treeDepth: 4