Assume you have a flat table that stores an ordered tree hierarchy:
Id Name ParentId Order
1 'Node 1' 0 10
2 'Node 1.1' 1 10
3 'Node 2' 0 20
4 'Node 1.1.1' 2 10
5 'Node 2.1' 3 10
6 'Node 1.2' 1 20
Here’s a diagram, where we have
[id] Name. Root node 0 is fictional.
 Node 1  Node 2
/ \ \
 Node 1.1  Node 1.2  Node 2.1
 Node 1.1.1
What minimalistic approach would you use to output that to HTML (or text, for that matter) as a correctly ordered, correctly indented tree?
Assume further you only have basic data structures (arrays and hashmaps), no fancy objects with parent/children references, no ORM, no framework, just your two hands. The table is represented as a result set, which can be accessed randomly.
Pseudo code or plain English is okay, this is purely a conceptional question.
Bonus question: Is there a fundamentally better way to store a tree structure like this in a RDBMS?
EDITS AND ADDITIONS
To answer one commenter’s (Mark Bessey‘s) question: A root node is not necessary, because it is never going to be displayed anyway. ParentId = 0 is the convention to express “these are top level”. The Order column defines how nodes with the same parent are going to be sorted.
The “result set” I spoke of can be pictured as an array of hashmaps (to stay in that terminology). For my example was meant to be already there. Some answers go the extra mile and construct it first, but thats okay.
The tree can be arbitrarily deep. Each node can have N children. I did not exactly have a “millions of entries” tree in mind, though.
Don’t mistake my choice of node naming (‘Node 1.1.1′) for something to rely on. The nodes could equally well be called ‘Frank’ or ‘Bob’, no naming structure is implied, this was merely to make it readable.
I have posted my own solution so you guys can pull it to pieces.
More Related Questions
- How to represent a data tree in SQL? I'm writing a data tree structure that is combined from a Tree and a TreeNode. Tree will contain the root and the top level actions on the data.
I'm using a UI library to present the tree […]
- hierarchical/tree database for directories in filesystem i want to store the directories present on the disk into a database with maintaining their hierarchical/tree structure.
Here's a fig,
- php / Mysql best tree structure I have to build a tree that will contain about 300 nodes inside it. The tree has no depth limitations. So it can have 3 or 15 levels. Each node can have an unlimited number of […]
- How to represent a tree like structure in a db I'm starting a project and I'm in the designing phase: I.e., I haven't decided yet on which db framework I'm going to use. I'm going to have code that creates a "forest" like structure. […]
- Binary Tree implementation using a recursive approach Project: "Create an implementation of a binary tree using the recursive approach introduced in the chapter. In this approach, each node is a binary tree. Thus a binary tree contains a […]
- NoSQL Database for hierarchical data What type of NoSQL database is best suited to store hierarchical data?
Say for example I want to store posts of a forum with a tree structure:
+ re: original post
+ re: […]
- Move node in nested set I'd need a MySQL query that moves a node and all its children within a nested set. I found this site, but that function just seems so illogical - there's no universeid or treeid in a […]
- Python: Recursive function for browsing all tree nodes I'm trying to make an recursive function which finds all nodes in a tree. My function, let's name it child(), can find all children of the current node and returns a list´of them.
- Maximum tree depth in Haskell I am given this type definition:
data Tree = Leaf Char | Branch2 Char Tree Tree | Branch3 Char Tree Tree Tree
How can I write a method that gives me the maximum path length of the tree […]
- Displaying a hierarchical tree with Baum in Laravel / Recursive functions in laravel So I've just installed the Baum package in Laravel and put together a small tree of categories.
I've been able to display the tree in nested JSON format with the getDependentsAndSelf() […]