0

I'm preparing for the data structures portion of an interview. I see that there are already questions about applications of binary trees in the real world - What are the applications of binary trees?

My question is different - How does one actually access nodes in data structures based on trees?

I understand BFS, DFS and such for explicit node traversal, I get a sense this is not how the real world works. Do people write their own traversal / search algorithms, or do they rely on iterators and similar access methods provided by the database?

What is the name of a high level abstraction of accessing structured tree data, if any? I'm thinking of iterators, but am not sure if this is the right term.

I am looking for a way to intelligently converse on the subject.

Alex Stone
  • 46,408
  • 55
  • 231
  • 407

1 Answers1

1

What is the name of a high level abstraction of accessing structured tree data, if any?

Iterator is something more suitable for linear data-structure like linked list or dynamic array. As tree is a hierarchical data-structure, parent(), child(), children(), ancestor(), descendent() are more suitable. For instance, if you want to implement a file system, you will have RootDirectory and to get all the sub-directories you might call like getAllSubDirectories() which are actually children of root directory. So the naming is actually domain specific.

class Directory {
   private Integer someAttribute;
   ....
   ....
   private Directory parentDirectory;
   List<Directory> subDirectories;
}

You can abstract as iterator and can call iterator.hasNext() or iterator.next() on a hierarchical data-structure as well. So for example, for a binary search tree, you can abstract away an iterator which can iterate the tree in preorder/inorder/postorder traversal in both direction. See in-order successor.

Kaidul
  • 15,409
  • 15
  • 81
  • 150