3
$\begingroup$

Suppose I have the following structure definition in C:

struct node {
    int value;
    struct node *parent, *left, *right;
}

If I want to represent a specific node inside a tree, all I need is a pointer to such node, which allows me to traverse the tree using the parent and children's link.

Instead, if I have a simple tree structure in a functional programming language, for example in Haskell

Data TreeNode a = Nil | Node a (TreeNode a) (TreeNode a)

is there a way to represent the concept of a node, which allows to explore the tree "locally"?

The question arises from approaching the lowest common ancestor problem, since I don't know even how to define the problem in a functional setting: what does it mean "taking in input two nodes"? Should one use a different tree representation?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

You are looking for the zipper data structure.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.