Python – Usage of a Binary Tree with List in Python

After the article here, concerning the building of the binary trees and their usefulness, today I will show how to use these trees in action 🙂

300px-Binary_tree.svg

Imagine that we have the following problem, used in arena.hackbulgaria.com:


Implement a program in Java, Python or C++ which starts with an initial list of number and then implements the following two commands. set [index] [value] – replaces the value at index in the list with the specified value. index <= length of the list. min [start_index] [end_index] – returns the minimum value from the elements between start_index and end_index. start_index <= end_index. Indices in both operations are zero-based. The first line of the input will contain two integers – the length of the list and the number of commands. The second line of the input will contain the elements of the list, separated by space. Each of the following lines will contain a single command in the format specified above.

Example
Input Output
16 8
19 11 15 4 7 13 11 2 3 5 12 7 23 17 4 6
min 0 4 4
min 5 10 2
set 4 3
min 4 8 2
min 0 6 3
set 15 8
min 15 15 8
min 10 13 7

And I have managed to achieve it with the help of a binary tree:

binaryTree

 

What have I done? Pretty much, I have made the following functions, to help me build the tree. This is their explanation, although their names are self-explanatory:

Pretty much, that is all. 🙂 The functions work as they are supposed to.

If you need the whole code, it is available in GitHub here:

Or simply below:

Enjoy it!

About

VBA Developer

Tagged with: , , , ,