Traversals on a Binary Search Tree

Computer Science Level 4

There is a binary search tree equipped with the following methods besides the usual ones:

def printLCR(node):
    if node.val == None:
        return
    printRLC(node.left)
    print(node.val)
    printRLC(node.right)

def printRLC(node):
    if node.val == None:
        return
    printLCR(node.right)
    printLCR(node.left)
    print(node.val)

The following data (in the following order) are inserted into the binary search tree:

10, 4, 17, 2, 15, 1, 6, 29, 9, 14, 13, 8, 16

If the output of printRLC is $a_0, a_1, \ldots, a_{12}$ , compute $\displaystyle\sum _{i=0} ^{12} {(i \times a_{i})}$ .

If something is not covered, it can be asked here . Changes will be made!

The answer is 699.

1 solution

Zeeshan Ali
Apr 28, 2018

The BST that we get by inserting the given set of values in order is as follows; And the printRLC(root) gives the following result; 16,13,14,15,17,29,1,2,4,8,9,6,10. Therefore; $\displaystyle\sum _{i=0} ^{12} {(i \times a_{i})}=0\times16+1\times13+2\times14+3\times15+4\times17+5\times29+6\times1+7\times2+8\times4+9\times8+10\times9+11\times6+12\times10=699$

Following is the python3 code;

Create the above BST and call printRLC(root) on that.

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

def insert(root, node):
    if not root:
        root = node
    else:
        if root.val < node.val:
            if not root.right:
                root.right = node
            else:
                insert(root.right, node)
        else:
            if not root.left:
                root.left = node
            else:
                insert(root.left, node)

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)        

def printLCR(root):
    if root:
        printRLC(root.left)
        print(root.val, end=',')
        printRLC(root.right)

def printRLC(root):
    if root:
        printLCR(root.right)
        printLCR(root.left)
        print(root.val, end=',')

VALUES = [10, 4, 17, 2, 15, 1, 6, 29, 9, 14, 13, 8, 16]

tree = Node(10)
for v in VALUES[1:]:
    insert(tree, Node(v))

print ("RESULT ", end="= ")
printRLC(tree)

1	`RESULT = 16,13,14,15,17,29,1,2,4,8,9,6,10,`

Using the above result we can now calculate the summation.

SUM = 0
RESULT = [16,13,14,15,17,29,1,2,4,8,9,6,10]
for i in range(len(RESULT)):
    SUM += i * RESULT[i]
print ("SUM =", SUM)

1	`SUM = 699`

Traversals on a Binary Search Tree

If something is not covered, it can be asked here . Changes will be made!

The answer is 699.

1 solution

0 pending reports