Programing Challenge: Constructing a Tree Given Its Edges.


Xah Lee

Programing Challenge: Constructing a Tree Given Its Edges.
Show you are the boss.

here's plain text.
────────── ────────── ────────── ────────── ──────────

Problem: given a list of edges of a tree: [child, parent], construct the tree. Here's a sample input: [[0, 2], [3, 0], [1, 4], [2, 4]].

Here's a sample print of a tree data structure:


this means, the root node's name is 4. It has 2 branches, named 1 and 2. The branche named 2 has 1 children, named 0, and it has one children named 3.The node's names are given as integers, but you can assume them to be strings.

You can choose your own data structure for the output. For example, nested list with 1st element being the node name, or use nested hash of hash, where key is the node name, and value is its children.

Here's sample data structure in python, using hash of hash.

"4": {
"1": {},
"2": {
"0": {
"3": {}

Other data structure are accepted.

Code it using your favorite language. I'll be able to look at and verify inMathematica, Python, Ruby, Perl, PHP, JavaScript, Emacs Lisp, Java. But other langs, such as Clojure and other lisps, OCaml, Haskell, erlang, Fortress, APL, HOL, Coq, Lua, Factor, Rust, Julia … are very welcome. 〔☛ Proliferation of Computing Languages〕

You should be able to do this within 8 hours from scratch. Took me 5 hours.

Python solution will be posted in a week, on 2014-01-14 (or sooner if many showed solutions). Post your solution in comment (or link to github or pastebin).

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Latest member

Latest Threads