0

I have a root tree stored in a SQL using materialized path (storing path string for each row).

What is the best way to visit each node node without starting from the root each time? Is materialized path right for my approach?

Harry
├── Jane
│   ├── Mark
│   └── Diane
│       ├── Mary
│       └── George
│           └── Jill
└── Bill

What I expect is that the code first starts at Harry and then visits Jane, Diane, George, Jill. In order to visit Mary, it will need to go back up one level from Jill, and visit Mary. Mary doesn't have any children, and we've visited every node in this level (George, Mary), so we go back up another level to visit Mark. No more children left on this level, so we go back up one level to Jane, but we've no other node on this level, so we go back up again. Finally, we have only Bill on this level, and visit him. When all the nodes have been visited, we are finished.

I thought also about storing each level of the tree in separate tables, and storing references to those tables in another table but this seems a bit inefficient because I'd have to store what level the traversal is currently on, and manipulate this data.

Level_0_table: Harry, Bill

Level_1_table: Jane

Level_2_table: Mark, Diane

Level_3_table: Mary, George

Level_4_table: Jill

KJW
  • 15,035
  • 47
  • 137
  • 243

1 Answers1

1

I'm not sure if "materialized paths" is the best data structure out there as it seems highly redundant. Perhaps you want to look for adjacency lists (that is, storing id, parent_id for every entry) or nested sets (storing the id, left and right neighbor IDs). Here is a nice overview over both structures. What you want is to perform a depth-first search (DFS) on your tree. Some time ago, the question was covered in this thread, so you might find it useful. There is a way of performing DFS by means of SQL queries, but the implementation will probably depend on the database software you use. In any case, you can implement DFS by using a stack to store the IDs of the elements you still need to visit. After every visit you push the children of the node onto the stack and proceed with the next popped element. Here is a nice example.

Community
  • 1
  • 1
Pavel
  • 7,436
  • 2
  • 29
  • 42
  • does DFS have backtracking? or is there another variant of DFS that specifically has this? – KJW May 29 '14 at 18:40
  • not by default, but you should be able to do it by pushing a tuple `(child, data)` onto the stack in order to be able to store partial paths or predecessor information or whatever you want in `data`. – Pavel May 29 '14 at 18:45