Building the binary tree

Problem

Given a list of child->parent relationships, build a binary tree out of it. All the element Ids inside the tree are unique. 

Example: 

Given the following relationships: 

Child Parent IsLeft 

15 20 true 

19 80 true 

17 20 false 

16 80 false 

80 50 false 

50 null false 

20 50 true 

You should return the following tree: 

       50 

       /   \ 

   20      80 

   /  \     /  \ 

15 17 19 16


Given the fact the input might not contain the node relationship information in order of top-to-bottom, we need to find a way to keep the created node somewhere to avoid creating a duplicate node. Also, it should be efficient to determine where the node in the relationship was created.

One way to do this is to use a hashtable containing the value of the node as a key and a pointer to the node as a value.

Now, we can iterate over the input relationship and start building the tree.
One thing to be careful of is that we need to remember the root node and return it at the end of the program.

We need to store the node whose parent is null.

Hashtable provides the constant search and inserts time of O(log N), where N is the number of nodes.

The loop statement over the input relation will be O(M), where M is the number of inputs.

Therefore, overall running time is O(M log N).

Here is the C++ solution



Practice statistics

3:31: think up the algorithm
14:33: write up the code
5:39: verifying the code (make minor change while copying the code into vi and found syntax error).

UPDATE(2022-06-11): solved the problem again in Python. 

06:00: to come up with the algorithm

15:00: finished the complete code with one mistake

04:00: to fix the mistake