Friday, July 15, 2011

Exercises on Tree

We all know the tree structure in data structures. We got some problems that can be solved using the python.

We have a list that contains values in tree manner. A list with only root value 10 is like,

[[],10,[]]

Here the left and right nodes are empty. When we add an element, say 5, in the right node then it will be like,

[[],10,[[],5,[]]

If we add 11 to left node,

[[[],11,[]],10,[[],5,[]]]

I think you got the idea. A list will always have a value in the middle and two inner lists to represent right and left nodes.

Our problems are,

  1. Just print the elements of the tree in any order.
  2. Find the total number of nodes.
  3. Find the height of the tree.

We use the recursion in these problems. Answers are given below.

Problem 1:

def treeprint(list1):
    for lista in list1:
        if isinstance(lista, list):
            liatb = treeprint(lista)
        else:
            print lista

Problem 2:

def treenode(list1):
    node = 0
    for lista in list1:
        if isinstance(lista, list):
            if len(lista) > 0 :
                listb = treenode(lista)
            else :
                listb = 0
        else:
            listb = 1
        node = node + listb
    return node

Problem 3:

def treeheight(list1):
    if len(list1) == 0:
        return 0
    left = 1 + treeheight(list1[0])
    right = 1 + treeheight(list1[2])
    if left > right:
        return left
    else:
        return right

Possible test values are,

[[],10,[]]
[[[],5,[]],10,[]]
[[[],5,[]],10,[[],6,[]]]

You can also download all the answer codes as a zip file. Click here.

Thanks

AJAY

No comments:

Post a Comment