Module 2, Practical 7

In this practical we will keep working with data structures. In particular, we will see a special data structure called tree.

Trees

Trees are data structures composed of two types of elements: nodes and edges.
Nodes represent objects and edges represent relationships among two nodes.
The node at the top level of the tree is called the root, and is connected to one or more other nodes.
If the root is connected to another node by means of one edge, then it is said to be the parent of the node (and that node is the child of the root).
Any node can be parent of one or more other nodes, but all nodes have only one parent.
The root is the only exception as it does not have any parent.
Finally, some nodes do not have children and they are called leaves.

An example of tree:

_images/tree.png

As seen in the lecture, trees can be defined recursively in the following way: a tree is a root and zero or more subtrees, each of which is also a tree. The root of each subtree is connected to the root of the parent tree by an edge.

Graphically:

_images/recursiveTree.png

Some properties of nodes and trees are:

  1. The depth of a node N: the length of the path connecting the root to N counted as number of edges in the path.

  2. The level (n) of a tree: set of nodes at the same depth (n).

  3. Height : is the maximum depth of all leaves.

  4. Width : the maximum number of nodes in each level.

The following tree:

_images/exampleTree.png

has four levels (0, 1, 2, 3), height equal to 3 and width equal to 4.

ADT: Binary Tree

Binary trees are trees where each node has at most two children: the right child and the left child.

_images/binaryPointers.png

The specifications of the binary tree ADT (from the lecture):

_images/binarytreeADT.png

When implementing a tree we could (similarly to what we did with linked lists) define a node object, and then a tree object that stores nodes, but we will use the more compact way which is to use the recursive definition of a tree.

Example: Let’s implement a binary tree using the recursive definition:
>a binary tree is a root –with a value – connected to two subtrees, respectively the right and left subtree.
[1]:
class BinaryTree:
    def __init__(self, value):
        self.__data = value
        self.__right = None
        self.__left = None
        self.__parent = None

    def getValue(self):
        return self.__data
    def setValue(self, newValue):
        self.__data = newValue

    def getParent(self):
        return self.__parent
    def setParent(self, tree):
        self.__parent = tree

    def getRight(self):
        return self.__right
    def getLeft(self):
        return self.__left

    def insertRight(self, tree):
        if self.__right == None:
            self.__right = tree
            tree.setParent(self)

    def insertLeft(self, tree):
        if self.__left == None:
            self.__left = tree
            tree.setParent(self)

    def deleteRight(self):
        self.__right = None

    def deleteLeft(self):
        self.__left = None

def printTree(root):
    cur = root
    #each element is a node and a depth
    #depth is used to format prints (with tabs)
    nodes = [(cur,0)]
    tabs = ""
    lev = 0
    while len(nodes) >0:
        cur, lev = nodes.pop(-1)
        #print("{}{}".format("\t"*lev, cur.getValue()))
        if cur.getRight() != None:
            print ("{}{} (r)-> {}".format("\t"*lev,
                                          cur.getValue(),
                                          cur.getRight().getValue()))
            nodes.append((cur.getRight(), lev+1))
        if cur.getLeft() != None:
            print ("{}{} (l)-> {}".format("\t"*lev,
                                          cur.getValue(),
                                          cur.getLeft().getValue()))
            nodes.append((cur.getLeft(), lev+1))

if __name__ == "__main__":
    BT = BinaryTree("Root")
    bt1 = BinaryTree(1)
    bt2 = BinaryTree(2)
    bt3 = BinaryTree(3)
    bt4 = BinaryTree(4)
    bt5 = BinaryTree(5)
    bt6 = BinaryTree(6)
    bt5a = BinaryTree("5a")
    bt5b = BinaryTree("5b")
    bt5c = BinaryTree("5c")

    BT.insertLeft(bt1)
    BT.insertRight(bt2)

    bt2.insertLeft(bt3)

    bt3.insertLeft(bt4)
    bt3.insertRight(bt5)
    bt2.insertRight(bt6)
    bt1.insertRight(bt5b)
    bt1.insertLeft(bt5a)
    bt5b.insertRight(bt5c)

    printTree(BT)

    print("\nDelete right branch of 2")
    bt2.deleteRight()
    printTree(BT)

    print("\nInsert left branch of 5")
    newN = BinaryTree("child of 5")
    bt5.insertLeft(newN)
    printTree(BT)
Root (r)-> 2
Root (l)-> 1
        1 (r)-> 5b
        1 (l)-> 5a
                5b (r)-> 5c
        2 (r)-> 6
        2 (l)-> 3
                3 (r)-> 5
                3 (l)-> 4

Delete right branch of 2
Root (r)-> 2
Root (l)-> 1
        1 (r)-> 5b
        1 (l)-> 5a
                5b (r)-> 5c
        2 (l)-> 3
                3 (r)-> 5
                3 (l)-> 4

Insert left branch of 5
Root (r)-> 2
Root (l)-> 1
        1 (r)-> 5b
        1 (l)-> 5a
                5b (r)-> 5c
        2 (l)-> 3
                3 (r)-> 5
                3 (l)-> 4
                        5 (l)-> child of 5

Download the complete source file: BinaryTree.py

Note that in the code above, to delete the right or left subtree you just set the pointer to null. This destroys the whole subtree (more clever things can be done in some cases, especially with generic trees).

Exercise

  1. Modify the BinaryTree class adding a depth parameter counting, for each subtree, its depth (i.e. distance from the root of the tree). Note that you have to update properly the depth when inserting a new node. Add a getDepth and setDepth method too.

  1. Test the code printing the depth of all the nodes of the binary graph:

_images/bintree_2bis.png

that can be created with:

BT = BinaryTree("Root")
bt1 = BinaryTree(1)
bt2 = BinaryTree(2)
bt3 = BinaryTree(3)
bt4 = BinaryTree(4)
bt5 = BinaryTree(5)
bt6 = BinaryTree(6)
bt5a = BinaryTree("5a")
bt5b = BinaryTree("5b")
bt5c = BinaryTree("5c")
bt7 = BinaryTree(7)
bt8 = BinaryTree(8)
BT.insertLeft(bt1)
BT.insertRight(bt2)
bt2.insertLeft(bt3)
bt3.insertLeft(bt4)
bt3.insertRight(bt5)
bt2.insertRight(bt6)
bt1.insertRight(bt5b)
bt1.insertLeft(bt5a)
bt5b.insertRight(bt5c)
bt4.insertRight(bt7)
bt4.insertLeft(bt8)

Show/Hide Solution

Tree visit

Now we can see how to perform some visits of the trees, that is going through the nodes following the connections.
In particular, there are two different types of visits: depth first and breadth first search.

Binary Tree visits: DFS

Given a tree T, depth first search (DFS) visits all the subtrees of T going as deep as it can before going back and down another branch until all the tree is visited.

DFS requires a stack and can be implemented recursively. What we do with the root during the visit defines 3 different types of visits:

  1. the root is visited before the visiting the subtree : pre-order;

  2. the root is visited after the left subtree but before the right subtree : in-order;

  3. the root is visited after the left and right subtrees : post-order.

Example: Let’s implement the three versions of DFS and apply them to the binary tree seen above.

[2]:
class BinaryTree:
    def __init__(self, value):
        self.__data = value
        self.__right = None
        self.__left = None
        self.__parent = None

    def getValue(self):
        return self.__data
    def setValue(self, newValue):
        self.__data = newValue

    def getParent(self):
        return self.__parent
    def setParent(self, tree):
        self.__parent = tree

    def getRight(self):
        return self.__right
    def getLeft(self):
        return self.__left

    def insertRight(self, tree):
        if self.__right == None:
            self.__right = tree
            tree.setParent(self)
    def insertLeft(self, tree):
        if self.__left == None:
            self.__left = tree
            tree.setParent(self)

    def deleteRight(self):
        self.__right = None
    def deleteLeft(self):
        self.__left = None

    def preOrderDFS(self):
        if self != None:
            r = self.getRight()
            l = self.getLeft()
            print(self.getValue()) # print before recursive calls!
            if l != None:
                l.preOrderDFS()
            if r != None:
                r.preOrderDFS()

    def inOrderDFS(self):
        if self != None:
            r = self.getRight()
            l = self.getLeft()
            if l != None:
                l.inOrderDFS()
            print(self.getValue()) # print in the between the recursive calls!
            if r != None:
                r.inOrderDFS()

    def postOrderDFS(self):
        if self != None:
            r = self.getRight()
            l = self.getLeft()
            if l != None:
                l.postOrderDFS()
            if r != None:
                r.postOrderDFS()
            print(self.getValue()) # print after the recursive calls!

def printTree(root):
    cur = root
    #each element is a node and a depth
    #depth is used to format prints (with tabs)
    nodes = [(cur,0)]
    tabs = ""
    lev = 0
    while len(nodes) >0:
        cur, lev = nodes.pop(-1)
        #print("{}{}".format("\t"*lev, cur.getValue()))
        if cur.getRight() != None:
            print ("{}{} (r)-> {}".format("\t"*lev,
                                          cur.getValue(),
                                          cur.getRight().getValue()))
            nodes.append((cur.getRight(), lev+1))
        if cur.getLeft() != None:
            print ("{}{} (l)-> {}".format("\t"*lev,
                                          cur.getValue(),
                                          cur.getLeft().getValue()))
            nodes.append((cur.getLeft(), lev+1))

if __name__ == "__main__":
    BT = BinaryTree("Root")
    bt1 = BinaryTree(1)
    bt2 = BinaryTree(2)
    bt3 = BinaryTree(3)
    bt4 = BinaryTree(4)
    bt5 = BinaryTree(5)
    bt6 = BinaryTree(6)
    bt5a = BinaryTree("5a")
    bt5b = BinaryTree("5b")
    bt5c = BinaryTree("5c")

    BT.insertLeft(bt1)
    BT.insertRight(bt2)

    bt2.insertLeft(bt3)

    bt3.insertLeft(bt4)
    bt3.insertRight(bt5)
    bt2.insertRight(bt6)
    bt1.insertRight(bt5b)
    bt1.insertLeft(bt5a)
    bt5b.insertRight(bt5c)

    printTree(BT)

    print("Pre-order DFS:")
    BT.preOrderDFS()
    print("\nIn-order DFS:")
    BT.inOrderDFS()
    print("\nPost-order DFS:")
    BT.postOrderDFS()
Root (r)-> 2
Root (l)-> 1
        1 (r)-> 5b
        1 (l)-> 5a
                5b (r)-> 5c
        2 (r)-> 6
        2 (l)-> 3
                3 (r)-> 5
                3 (l)-> 4
Pre-order DFS:
Root
1
5a
5b
5c
2
3
4
5
6

In-order DFS:
5a
1
5b
5c
Root
4
3
5
2
6

Post-order DFS:
5a
5c
5b
1
4
5
3
6
2
Root

Download the complete source file: BinaryTreeDFSVisits.py

Compare the results above with the graph:

_images/bintree_2.png

Binary Tree visits: BFS

Breadth first search visits all the higher levels of a tree before going down. Basically, this search goes as wide as it can before going deep.

This visit makes use of a queue: for each tree, it adds the left and right subtrees to the queue and recursively visits them in the order they have been pushed into the queue.

As said, implementations of BFS make use of a FIFO queue. In Python, we can use the efficient deque data structure that is implemented in the collections module (remember to import it first with from collections import deque and use deque.append to add at the end and deque.popleft to remove from the beginning).

Example: Let’s implement a BFS method and apply it to binary tree seen above.

[6]:
from collections import deque

class BinaryTree:
    def __init__(self, value):
        self.__data = value
        self.__right = None
        self.__left = None
        self.__parent = None

    def getValue(self):
        return self.__data
    def setValue(self, newValue):
        self.__data = newValue

    def getParent(self):
        return self.__parent
    def setParent(self, tree):
        self.__parent = tree

    def getRight(self):
        return self.__right
    def getLeft(self):
        return self.__left

    def insertRight(self, tree):
        if self.__right == None:
            self.__right = tree
            tree.setParent(self)
    def insertLeft(self, tree):
        if self.__left == None:
            self.__left = tree
            tree.setParent(self)

    def deleteRight(self):
        self.__right = None
    def deleteLeft(self):
        self.__left = None

    def BFS(self):
        if self != None:
            level = deque()
            level.append(self)

            while len(level) > 0:
                #print(len(level))
                cur = level.popleft()
                print(cur.getValue())
                r = cur.getRight()
                l = cur.getLeft()
                if l != None:
                    #print("from {} Appending: {}".format(cur.getValue(),
                    #                                      l.getValue()))
                    level.append(l)
                if r != None:
                    level.append(r)
                    #print("from {} Appending: {}".format(cur.getValue(),
                    #                                     r.getValue()))

def printTree(root):
    cur = root
    #each element is a node and a depth
    #depth is used to format prints (with tabs)
    nodes = [(cur,0)]
    tabs = ""
    lev = 0
    while len(nodes) >0:
        cur, lev = nodes.pop(-1)
        #print("{}{}".format("\t"*lev, cur.getValue()))
        if cur.getRight() != None:
            print ("{}{} (r)-> {}".format("\t"*lev,
                                          cur.getValue(),
                                          cur.getRight().getValue()))
            nodes.append((cur.getRight(), lev+1))
        if cur.getLeft() != None:
            print ("{}{} (l)-> {}".format("\t"*lev,
                                          cur.getValue(),
                                          cur.getLeft().getValue()))
            nodes.append((cur.getLeft(), lev+1))

if __name__ == "__main__":
    BT = BinaryTree("Root")
    bt1 = BinaryTree(1)
    bt2 = BinaryTree(2)
    bt3 = BinaryTree(3)
    bt4 = BinaryTree(4)
    bt5 = BinaryTree(5)
    bt6 = BinaryTree(6)
    bt5a = BinaryTree("5a")
    bt5b = BinaryTree("5b")
    bt5c = BinaryTree("5c")

    BT.insertLeft(bt1)
    BT.insertRight(bt2)
    bt2.insertLeft(bt3)
    bt3.insertLeft(bt4)
    bt3.insertRight(bt5)
    bt2.insertRight(bt6)
    bt1.insertRight(bt5b)
    bt1.insertLeft(bt5a)
    bt5b.insertRight(bt5c)

    printTree(BT)

    print("BFS:")
    BT.BFS()
Root (r)-> 2
Root (l)-> 1
        1 (r)-> 5b
        1 (l)-> 5a
                5b (r)-> 5c
        2 (r)-> 6
        2 (l)-> 3
                3 (r)-> 5
                3 (l)-> 4
BFS:
Root
1
2
5a
5b
3
6
5c
4
5

Download the complete source file: BinaryTreeBFSVisit.py

Compare the results above with the graph:

_images/bintree_2.png

Exercises

  1. The width of a binary tree T is the largest number of nodes that belong to the same level. The minimal height of a binary tree T is the minimal distance between the root and its closest leaf in its subtree. This distance is counted in number of nodes.

Given the BinaryTree defined above:

  1. Write a function getWidth(T) that given a tree T, returns the width of T. Hint: get all nodes at each level and count them.

  2. Write a function getMinHeight(T) that given a tree T, returns the minimal height of T (in number of nodes). Hint: stop at first level with a leaf (similar to previous function).

  3. Write a function nodesAtLevel(T,k) that given a binary tree T and an integer k, returns the nodes at level k.

Test the functions with the following binary graph:

_images/bintree_2tris.png

that can be created with:

BT = BinaryTree("Root")
bt1 = BinaryTree(1)
bt2 = BinaryTree(2)
bt3 = BinaryTree(3)
bt4 = BinaryTree(4)
bt5 = BinaryTree(5)
bt6 = BinaryTree(6)
bt5a = BinaryTree("5a")
bt5b = BinaryTree("5b")
bt5c = BinaryTree("5c")
bt7 = BinaryTree(7)
bt8 = BinaryTree(8)
bt9 = BinaryTree(9)
bt10 = BinaryTree(10)
BT.insertLeft(bt1)
BT.insertRight(bt2)
bt2.insertLeft(bt3)
bt3.insertLeft(bt4)
bt3.insertRight(bt5)
bt2.insertRight(bt6)
bt1.insertRight(bt5b)
bt1.insertLeft(bt5a)
bt5b.insertRight(bt5c)
bt4.insertRight(bt7)
bt4.insertLeft(bt8)
bt6.insertRight(bt10)
bt6.insertLeft(bt9)

Show/Hide Solution

  1. Given the BinaryTree used so far, implement a getCommonAncestor(n1,n2) method that gets the common ancestor between the two nodes n1 and n2.

_images/bintree_2tris.png

For example, considering the graph above:

getCommonAncestor(7,5) = 3
getCommonAncestor(7,10) = 2
getCommonAncestor(8,5b) = Root

Show/Hide Solution

  1. A Binary Search Tree is a binary tree with the following properties:

  • The left subtree of a node contains only nodes with values lower than that of the node.

  • The right subtree of a node contains only nodes with values greater than the node’s.

  • No duplicate nodes are allowed.

Implement:

  1. a function BST = createBST(inList) that gets a list of integers (or strings) and returns a BinaryTree that is a Binary Search Tree;

  2. a search function searchBST(BST, element) that gets an integer (or string) and checks if it is present in the Binary Search Tree.

  3. modify the inOrderDFS(self) method to return a list of visited nodes using in-order depth first search. Test the method by printing the first 100 elements to show that they are actually sorted (this is a sorting algorithm indeed!);

Test the code with the following intList:

import random
intList = []
for i in range(1000):
    inList.append(random.randint(0,10000))

Show/Hide Solution

ADT: Generic Tree

Generic Trees are like binary trees, but each node can have more than 2 children. One possible implementation is that each node (that is a subtree in itself) has a value, a link to its parent and a list of children.

Another implementation is that each node has a value, a link to its parent, a link to its next sibling and a link to its first child:

_images/genericTreePointers.png

We will be using this latter implementation of the tree.

The Generic Tree ADT seen at lecture follows:

_images/genericTreeADT.png

Given the following generic tree:

_images/gentree_1.png

Exercise (implementation)

  1. Implement the GenericTree class representing the ADT seen above and create the tree in the picture above.

Show/Hide Solution