CareerCup

C++ version using recursion. First I sort the elements by parent: O(nlogn). Then I do a binary search O(logn) to find each parent on the list and recursively print it's children.

Output:

A (parent id = null)
  B (parent id = A)
    C (parent id = B)
      D (parent id = C)
    H (parent id = B)
  E (parent id = A)
    F (parent id = E)
      G (parent id = F)

Code:

#include <iostream>
#include <vector>
#include <algorithm>

template <typename T>
struct node {
    typedef T value_type;
    
	node(T id, T parent_id) : id_(id), parent_id_(parent_id) { }
	node(T id) : id_(id), parent_id_(0) { }
    
	T id_;
	T parent_id_;
};

template <typename T>
std::ostream& operator<<(std::ostream& os, const node<T>& n) {
	os << n.id_ << " (parent id = ";
	if (!n.parent_id_)
		os << "null)";
	else
		os << n.parent_id_ << ")";
	os << std::endl;
	return os;
}

template <typename T>
struct order_by_parent {
	bool operator()(const node<T>& a, const node<T>& b) {
		// Is it the root?
		if (!a.parent_id_)
			return true;
        
		// Is  the same parent?
		if (a.parent_id_ == b.parent_id_) {
			// Order by id
			return a.id_ < b.id_;
		}
		
		// Else, order by parent
		return a.parent_id_ < b.parent_id_;
	}
};

template <typename T>
struct find_by_parent {
	bool operator()(const node<T>& a, const node<T>& b) {
		return a.parent_id_ < b.parent_id_;
	}
};

template <typename ForwardIt>
void print_children_tree(ForwardIt begin, ForwardIt end, int indent) {
	
	// Base case
	if (begin >= end)
		return;
    
    typename ForwardIt::value_type node = *begin;

    // Print node
    for (int i = 0; i < indent; i++)
        std::cout << "  ";
    std::cout << node;
    
	// Binary search all childrens of this node
    typename ForwardIt::value_type parent(0, node.id_);
	ForwardIt it = std::lower_bound(begin, end, parent, find_by_parent<typename ForwardIt::value_type::value_type>());
	if (it == end) {
        // No children for this node.
		return;
	}
	
	// Print all children
	for (;;) {
		const typename ForwardIt::value_type& curr_n = *it;
		if (curr_n.parent_id_ != node.id_)
			break;
        
		// Recurse
		print_children_tree(it++, end, indent + 1);
	}
}

template <typename ForwardIt>
void print_tree(ForwardIt begin, ForwardIt end) {
	// Print children
	print_children_tree(begin, end, 1);
}

int main() {
	// Create the nodes
	std::vector<node<char>> nodes{{'A'}, {'B', 'A'}, {'C', 'B'}, {'D', 'C'},
        {'H', 'B'}, {'E', 'A'}, {'F', 'E'},
        {'G', 'F'}};
    
	// Sort all nodes by parent
	std::sort(nodes.begin(), nodes.end(), order_by_parent<char>());
	
	// Print all the nodes
	print_tree(nodes.begin(), nodes.end());
}