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?

$\endgroup$

1 Answer 1

5
$\begingroup$

You are looking for the zipper data structure.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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