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

	#include<map>
	#include<iostream>
	#include <list>
	#include <vector>
	using namespace std;
	struct node {
	node* left;
	node* right;
	int value;
	node(int v): value(v), left(0), right(0){}
	};
	struct relation {
	int child;
	int parent;
	bool is_left;
	relation(int c, int p, bool left):child(c), parent(p), is_left(left){}
	};
	node * build_tree(vector<relation>& input)
	{
	node * root = 0;
	map<int, node*> list;
	map<int, node*>::iterator found;
	for (int i = 0; i < input.size(); i++)
	{
	node *p=0, *c=0;
	if ((found = list.find(input[i].child)) != list.end())
	{
	c = found->second;
	}
	else
	{
	c = new node(input[i].child);
	list[c->value] = c;
	}
	if (input[i].parent != INT_MIN)
	{
	if ((found = list.find(input[i].parent)) != list.end())
	{
	p = found->second;
	}
	else
	{
	p = new node(input[i].parent);
	list[p->value] = p;
	}
	}
	if (p)
	{
	if (input[i].is_left)
	p->left = c;
	else
	p->right = c;
	} else {
	root = c;
	}
	}
	return root;
	}
	void print_tree(node * r)
	{
	int n_cur = 1;
	int n_next = 0;
	node* cur = 0;
	list<node*> queue;
	queue.push_back(r);
	while(queue.size())
	{
	cur = queue.front();
	queue.pop_front();
	n_cur--;
	cout <<cur->value<<" ";
	if (cur->left)
	{
	queue.push_back(cur->left);
	n_next++;
	}
	if (cur->right)
	{
	queue.push_back(cur->right);
	n_next++;
	}
	if (!n_cur)
	{
	n_cur = n_next;
	n_next = 0;
	cout<<endl;
	}
	}
	}
	int main()
	{
	vector<relation> input;
	input.push_back(relation(15,20, true));
	input.push_back(relation(19,80, true));
	input.push_back(relation(17,20, false));
	input.push_back(relation(16,80, false));
	input.push_back(relation(80,50, false));
	input.push_back(relation(50,INT_MIN, false));
	input.push_back(relation(20,50, true));
	node * result = build_tree(input);
	print_tree(result);
	return 1;
	}

view raw build_binary_tree.cpp hosted with ❤ by GitHub

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. 

	def print_inorder(node):
	if node == None:
	return
	print_inorder(node.left)
	print ("{}".format(node.value))
	print_inorder(node.right)
	# code
	class Node:
	def __init__(self, value, parent=None):
	self.parent = parent
	self.value = value
	self.right = None
	self.left = None
	def build_bst(inputs):
	root = None
	# hash map for nodes
	node_map = {}
	for input in inputs:
	# check if child exists
	if input[0] not in node_map:
	node_map[input[0]] = Node(input[0])
	child = node_map[input[0]]
	if input[1] == None:
	root = child
	elif input[1] not in node_map:
	node_map[input[1]] = Node(input[1])
	parent = node_map[input[1]] if input[1] != None else input[1]
	child.parent = parent
	if parent != None:
	if input[2] == True:
	parent.left = child
	else:
	parent.right = child
	return root
	# test
	input = [
	[15, 20, True],
	[19, 80, True],
	[17, 20, False ],
	[16, 80, False],
	[80, 50, False],
	[50, None, False],
	[20, 50, True]
	]
	tree = build_bst(input)
	print_inorder(tree)

view raw build_binary_tree.py hosted with ❤ by GitHub

06:00: to come up with the algorithm

15:00: finished the complete code with one mistake

04:00: to fix the mistake