June 7, 2019 Problem of the Week: On Binary Search Trees

This week, let’s take a look at the division 1, level two problem statement from SRM 750, SimulateBST. Find the problem statement here – https://community.topcoder.com/stat?c=problem_statement&pm=15302

The summary of the problem statement is that given a sequence of integers, generate a BST and calculate a certain checksum that is a function of each node’s value and depth. The problem statement also asks you to ignore repeated values.

Ultimately, the problem statement requires you to develop an algorithm to generate a binary search tree and maintain each node’s depth and values – and then plug them into the final checksum equation.

Let’s discuss our algorithm now.

The first element would assume the role of the root. The consequent element would either become the root’s left or right child. And further elements will descend and become a child of some node present in the tree.

In general, a node needs to be passed onto the right subtree of a node if its value exceeds that of the current node, or else to the left subtree. If the subtree doesn’t exist then this is where the node must be inserted, and its depth must be initialized.

Thus, when a node is inserted, it’ll eventually either become some node’s left or right child.

The incoming node will act as a node’s left child if its value is less than the other node’s, while if the input node exceeds the other node in value, it will become the right child.

In general, a node can be the left child of a node whose value exceeds it – or the right child of a node whose value is lesser than it.

Consider the sequence (6,9,7,8,5,10)

6 will become the root.

9 will become the right child of 6.

7 will become the left child of 9.

8 will become the right child of 7.

5 will become the left child of 6.

10 will become the right child of 9.

The key idea is that an incoming node can only become children of a node that’s either immediately less than it in terms of value – or one that’s immediately greater than it in terms of value.

Thus if the left child of the node immediately exceeding the incoming node already exists, then that would imply that there already exists a node that’s lesser than the incoming node – therefore the incoming node should be placed as the right child of this smaller node.

Computing the depths of these nodes is easy, as when inserting nodes into the BST, the depth of a node is equal to 1 + the depth of its parent.

By performing the above across the entire input sequence, we compute the depths and values of all nodes in the BST, allowing us now to compute the checksum and return it.
Topcoder member rosi (http://www.topcoder.com/tc?module=MemberProfile&cr=40857180&tab=alg) solved this the first, in C++ and their submission is available at – https://community.topcoder.com/stat?c=problem_solution&cr=40857180&rd=17399&pm=15302