10 ms·

The Great Tree-List Recursion Problem (2000)

brianberns 9y ago
In a time where we're finally realizing the benefits of functional programming (i.e. no side effects), a problem like this really seems like a callback to a more barbaric era. Like writing a state machine using gotos. EDIT: Never expected this to devolve into an argument about the merits of gotos! I thought we were all past that, but apparently not.
- nialo 9y ago
  Asking honestly because I would like to know: What is wrong with writing a state machine using gotos? Assuming that one is solving a problem that definitely needs a state machine for some reason.
  - brianberns 9y ago
    Gotos are generally considered a bad idea in high-level programming. http://www.u.arizona.edu/~rubinson/copyright_violations/Go_To_Considered_Harmful.html http://www.u.arizona.edu/~rubinson/copyright_violations/Go_T...
    - CoolGuySteve 9y ago
      This is lazy thinking, the gotos described in that essay can jump anywhere in the program while modern gotos are limited to the function scope and have various warnings about initialization order and whatnot. All the arguments it makes no longer apply but people still quote the snappy headline. That essay does make an excellent argument against programming with many tiny functions though, as those do cause the execution cursor to jump all over the source code document.
    - _jal 9y ago
      It seems to me that a substantial fraction of the people who quote that paper, assuming they have even read it, have failed to think critically about it.
    - mcguire 9y ago
      https://maniagnosis.crsr.net/2011/11/link-o-day-donald-knuth-tony-hoare-and.html https://maniagnosis.crsr.net/2011/11/link-o-day-donald-knuth...
  - cabalamat 9y ago
    > What is wrong with writing a state machine using gotos? Nothing. But the thing they want to do -- altering the datastructure on the fly -- is not the best way to solve the problem. I would solve this by writing two functions: one that creates an array from a binary tree, and one that creates a doubly-linked list from an array. Would this use up more RAM and take longer to run? Yes Would the code be easier to understand (and therefore more bug-free)? Yes
  - kabdib 9y ago
    Nothing wrong with goto, as long as it's clear. Many programmers treat 'goto' the same way that we treat radioactive waste, but they don't know why. Perhaps it is a holdover from courses with teachers who automatically graded 'fail' on programs that used a goto. Perhaps the programmers have only heard that gotos were bad. Sometimes 'goto' is the correct answer. For state machines it can be an pretty efficient technique. For "ordinary" code it is sometimes the best way out of a situation (e.g., busting out of a deeply nested set of loops). The "Goto considered harmful" movement came out of the 1970s, when GOTO was used all the time and the normal state for a big project was abject spaghetti. I think we can all agree that was a very bad thing. But the utter avoidance of goto is an overreaction that seems to be based on unreasoning fear, or toxic peer pressure.
    - posterboy 9y ago
      >busting out of a deeply nested set of loops so, goto is efficient at escaping inefficiently structured code? That doesn't make it really efficient. I mean there's a reasonable rule of thumb: don't indent the code too deep. Because what you are talking about is one kind of spaghetti, the kind cut into digestable chunks. The interleaving of active and inactive blocks leads to unreadable code sooner or later.
  - eternalban 9y ago
    It's "barbaric", kinda like eating with your hands. Of course this type of dogmatism gives us FP gems akin to [eating] a piece of Sushi with a steak knife.
- klodolph 9y ago
  Gotos are a natural choice for state machines, we basically emulate goto when we use while+switch or while+function pointer. The "goto considered harmful" paper is about structured programming, saying that you should use structured programming instead of goto, but it doesn't apply here because goto is the right structure to begin with. I suggest reading the actual "goto" paper sometime… it's a classic.
  - marcosdumay 9y ago
    I just want to add that the "goto" criticized on that paper does not exist anymore in any modern language (that includes C). Goto has been nerfed into something that can not destroy structured programming. But I do think the while+switch representation is superior.
    - klodolph 9y ago
      The while+switch, to me, looks like goto with extra typing. state = START; break; Translates directly to: goto start; Except while+switch is nicer if you have transition tables. YMMV
      - marcosdumay 9y ago
        Yes, but it forces you to keep your state as data, and makes it much more clear how the data relates to the code. But it does make for the same exact behavior.
        klodolph 9y ago
        The state is data either way... either an explicit variable or the program counter. With goto, the compiler is more likely to be able to see across state change boundaries (e.g. phi() will work correctly without doing anything fancy). So you can, e.g., have the compiler help you out by giving you warnings for uninitialized variables, when the variables are initialized in one state and used in another.
    - zokier 9y ago
- mcguire 9y ago
  Pssst! Lambda, the ultimate goto. http://library.readscheme.org/page1.html http://library.readscheme.org/page1.html
- deleted 9y ago
  [deleted]
- Zelizz 9y ago
  You could always clone the tree into a new linked-list if you wanted to keep things purely functional, but that would add needless complexity and still not make it easier to create a correct implementation. Functional programming as a paradigm makes sense when you want to limit the context a programmer has to be aware of when working on a problem, but in this case recursion and imperative programming accomplish the same goal.
amelius 9y ago
Not really a useful problem, considering that it will be impossible to solve if the tree would be properly balanced.
- junke 9y ago
  What do you mean?
- sigjuice 9y ago
  I think it is irrelevant whether the binary search tree is balanced or not. Why do you think it matters?
- mbrumlow 9y ago
  I don't agree. The tree being balanced of not has not bearing on the solvability of the problem. Even a naive approach would work balanced or unbalanced and that would be simply to pop the lowest value in the tree and construct your list until you run out of nodes. The trick is to do it in O(n) time and use recursion.
llimllib 9y ago
Neat! Also the C answer is missing a brace at the end of treeToList and that makes me a little crazy
- deleted 9y ago
  [deleted]
cbarrick 9y ago
Isn't this just in-order traversal... class Linked: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right def tree_to_list(self): if self.left is not None: first, left = self.left.tree_to_list() left.right = self self.left = left else: first = self if self.right is not None: right, last = self.right.tree_to_list() right.left = self self.right = right else: last = self first.left = last last.right = first return first, last
pklausler 9y ago
The reversed problem is more interesting: given a doubly-linked sorted list (and its length), convert it to a balanced binary search tree.
- sigjuice 9y ago
  https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-16.html#%_thm_2.64 https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-16.htm...
- cbarrick 9y ago
  That's the DSW algorithm. https://en.wikipedia.org/wiki/Day-Stout-Warren_algorithm https://en.wikipedia.org/wiki/Day-Stout-Warren_algorithm
  - nine_k 9y ago
    Pretty trivial, since you can easily find the middle of a doubly-linked list and step back. Then you simply do "find middle, use it as root, recursively build two subtrees". With a singly-linked list, it's much harder; I don't know (without googling) if a more efficient than "build and rebalance as you go" algorithm exists.
    - pklausler 9y ago
      If you know the length of the initial list (and that's obviously possible in O(N)), it's all easy.
    - tzs 9y ago
      You could convert a singly-linked list to a doubly-linked list in O(n), and then apply your favorite doubly-linked solution. You could even do this in place without increasing the size of each node at the cost of doubling the size of variables that point to nodes and slightly lowing down stepping through the list. You do this by storing the next and previous pointers for each node in the same location, xor'ed together. That doubles the size of variables that point to nodes and slows down stepping because you have to turn them into structs that store both a pointer to the node and a pointer to an adjacent node and update both of these pointers as you move through the list.
zmonx 9y ago
The declarative programming language Prolog is very suitable for reasoning about trees, lists and recursive structures in general. For example, here is a Prolog definition of the tree from the article: tree(node(4, node(2, node(1,nil,nil), node(3,nil,nil)), node(5,nil,nil))). I am using terms of the form nil/0 and node/3 to represent the tree. Let us start by converting the tree to a list. As requested, we shall consider the in-order traversal of the tree elements, described as a list. For such situations, Prolog DCG notation is very convenient, since it easily allows us to describe a list in relation to other terms (in this case, a tree): tree_to_list(nil) --> []. tree_to_list(node(E,Left,Right)) --> tree_to_list(Left), [E], tree_to_list(Right). Here is a sample query and its result: ?- tree(T), phrase(tree_to_list(T), Ls). T = node(4, ...), Ls = [1, 2, 3, 4, 5]. OK, so we now have the in-order traversal. Of course, lists are already implicitly "linked" in Prolog in one direction: Given a list, we can readily reason about the first element and the remaining elements. The task requires us to do more, i.e., reason about the reverse direction as well. One way to express this is to use rational trees, also known as cyclic terms in Prolog. For example, here is a case of cyclic term: ?- append([a,b,c], Ls, Ls). Ls = [a, b, c|Ls]. Here, Ls represents the circular list [a,b,c,a,b,c,a,...]. We can use this feature to our advantage as follows: list_with_backlinks([], []). list_with_backlinks([L|Ls0], [L-Prev|Ls]) :- append([L|Ls], Cs, Cs), foldl(with_backlink, Ls0, Ls, Cs, Prev). with_backlink(E, E-Cs0, Cs0, Cs) :- Cs0 = [_|Cs]. Sample query and answer: ?- list_with_backlinks([a,b,c], Cs). Cs = [a-[_S2|_S1], b-_S1, _S2], % where _S1 = [a, b-_S1, _S2|_S1], _S2 = c-[b-_S1, _S2|_S1] . Thus, as desired, we can generate a doubly-linked list from the original tree: ?- tree(T), phrase(tree_to_list(T), Ls0), list_with_backlinks(Ls0, Ls). T = node(4, ...), Ls0 = [1, 2, 3, 4, 5], Ls = [1-[_S4|_S1], 2-_S1, _S2, _S3, _S4], % where _S1 = [1, 2-_S1, _S2, _S3, _S4|_S1], _S2 = 3-[2-_S1, _S2, _S3, _S4|_S1], _S3 = 4-[_S2, _S3, _S4|_S1], _S4 = 5-[_S3, _S4|_S1] . Of course, this does not completely solve the task, which requires in-place modifications of the original tree. Pure Prolog lacks destructive modifications, so we cannot fully translate the code to Prolog. On the plus side, no pointers at all were necessary, and the recursions are pretty straight-forward.
atilimcetin 9y ago
This is one of the problems in 'Elements of Programming Interviews' book. - Convert a sorted doubly linked list into a BST C++: http://elementsofprogramminginterviews.com/solutions/cpp/sorted_list_to_bst.cc http://elementsofprogramminginterviews.com/solutions/cpp/sor... Java: http://elementsofprogramminginterviews.com/solutions/java/SortedListToBST.java http://elementsofprogramminginterviews.com/solutions/java/So... Python: http://elementsofprogramminginterviews.com/solutions/python/sorted_list_to_bst.py http://elementsofprogramminginterviews.com/solutions/python/... - Convert a BST to a sorted doubly linked list C++: http://elementsofprogramminginterviews.com/solutions/cpp/bst_to_sorted_doubly_list.cc http://elementsofprogramminginterviews.com/solutions/cpp/bst... Java: http://elementsofprogramminginterviews.com/solutions/java/BSTToSortedDoublyList.java http://elementsofprogramminginterviews.com/solutions/java/BS... Python: http://elementsofprogramminginterviews.com/solutions/python/bst_to_sorted_doubly_list.py http://elementsofprogramminginterviews.com/solutions/python/...
kazinator 9y ago
Here is a C library I wrote in 1999 which can convert, in-place, a container between Red-Black, AVL and linked list: http://www.kylheku.com/~kaz/austin.html http://www.kylheku.com/~kaz/austin.html

In a time where we're finally realizing the benefits of functional programming (i.e. no side effects), a problem like this really seems like a callback to a more barbaric era. Like writing a state machine using gotos. EDIT: Never expected this to devolve into an argument about the merits of gotos! I thought we were all past that, but apparently not.

nialo 9y ago
Asking honestly because I would like to know: What is wrong with writing a state machine using gotos? Assuming that one is solving a problem that definitely needs a state machine for some reason.
- brianberns 9y ago
  Gotos are generally considered a bad idea in high-level programming. http://www.u.arizona.edu/~rubinson/copyright_violations/Go_To_Considered_Harmful.html http://www.u.arizona.edu/~rubinson/copyright_violations/Go_T...
  - CoolGuySteve 9y ago
    This is lazy thinking, the gotos described in that essay can jump anywhere in the program while modern gotos are limited to the function scope and have various warnings about initialization order and whatnot. All the arguments it makes no longer apply but people still quote the snappy headline. That essay does make an excellent argument against programming with many tiny functions though, as those do cause the execution cursor to jump all over the source code document.
  - _jal 9y ago
    It seems to me that a substantial fraction of the people who quote that paper, assuming they have even read it, have failed to think critically about it.
  - mcguire 9y ago
    https://maniagnosis.crsr.net/2011/11/link-o-day-donald-knuth-tony-hoare-and.html https://maniagnosis.crsr.net/2011/11/link-o-day-donald-knuth...
- cabalamat 9y ago
  > What is wrong with writing a state machine using gotos? Nothing. But the thing they want to do -- altering the datastructure on the fly -- is not the best way to solve the problem. I would solve this by writing two functions: one that creates an array from a binary tree, and one that creates a doubly-linked list from an array. Would this use up more RAM and take longer to run? Yes Would the code be easier to understand (and therefore more bug-free)? Yes
- kabdib 9y ago
  Nothing wrong with goto, as long as it's clear. Many programmers treat 'goto' the same way that we treat radioactive waste, but they don't know why. Perhaps it is a holdover from courses with teachers who automatically graded 'fail' on programs that used a goto. Perhaps the programmers have only heard that gotos were bad. Sometimes 'goto' is the correct answer. For state machines it can be an pretty efficient technique. For "ordinary" code it is sometimes the best way out of a situation (e.g., busting out of a deeply nested set of loops). The "Goto considered harmful" movement came out of the 1970s, when GOTO was used all the time and the normal state for a big project was abject spaghetti. I think we can all agree that was a very bad thing. But the utter avoidance of goto is an overreaction that seems to be based on unreasoning fear, or toxic peer pressure.
  - posterboy 9y ago
    >busting out of a deeply nested set of loops so, goto is efficient at escaping inefficiently structured code? That doesn't make it really efficient. I mean there's a reasonable rule of thumb: don't indent the code too deep. Because what you are talking about is one kind of spaghetti, the kind cut into digestable chunks. The interleaving of active and inactive blocks leads to unreadable code sooner or later.
- eternalban 9y ago
  It's "barbaric", kinda like eating with your hands. Of course this type of dogmatism gives us FP gems akin to [eating] a piece of Sushi with a steak knife.
klodolph 9y ago
Gotos are a natural choice for state machines, we basically emulate goto when we use while+switch or while+function pointer. The "goto considered harmful" paper is about structured programming, saying that you should use structured programming instead of goto, but it doesn't apply here because goto is the right structure to begin with. I suggest reading the actual "goto" paper sometime… it's a classic.
- marcosdumay 9y ago
  I just want to add that the "goto" criticized on that paper does not exist anymore in any modern language (that includes C). Goto has been nerfed into something that can not destroy structured programming. But I do think the while+switch representation is superior.
  - klodolph 9y ago
    The while+switch, to me, looks like goto with extra typing. state = START; break; Translates directly to: goto start; Except while+switch is nicer if you have transition tables. YMMV
    - marcosdumay 9y ago
      Yes, but it forces you to keep your state as data, and makes it much more clear how the data relates to the code. But it does make for the same exact behavior.
      - klodolph 9y ago
        The state is data either way... either an explicit variable or the program counter. With goto, the compiler is more likely to be able to see across state change boundaries (e.g. phi() will work correctly without doing anything fancy). So you can, e.g., have the compiler help you out by giving you warnings for uninitialized variables, when the variables are initialized in one state and used in another.
  - zokier 9y ago
mcguire 9y ago
Pssst! Lambda, the ultimate goto. http://library.readscheme.org/page1.html http://library.readscheme.org/page1.html
deleted 9y ago
[deleted]
Zelizz 9y ago
You could always clone the tree into a new linked-list if you wanted to keep things purely functional, but that would add needless complexity and still not make it easier to create a correct implementation. Functional programming as a paradigm makes sense when you want to limit the context a programmer has to be aware of when working on a problem, but in this case recursion and imperative programming accomplish the same goal.

amelius 9y ago

Not really a useful problem, considering that it will be impossible to solve if the tree would be properly balanced.

junke 9y ago
What do you mean?
sigjuice 9y ago
I think it is irrelevant whether the binary search tree is balanced or not. Why do you think it matters?
mbrumlow 9y ago
I don't agree. The tree being balanced of not has not bearing on the solvability of the problem. Even a naive approach would work balanced or unbalanced and that would be simply to pop the lowest value in the tree and construct your list until you run out of nodes. The trick is to do it in O(n) time and use recursion.

llimllib 9y ago

Neat! Also the C answer is missing a brace at the end of treeToList and that makes me a little crazy

deleted 9y ago
[deleted]

cbarrick 9y ago

Isn't this just in-order traversal... class Linked: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right def tree_to_list(self): if self.left is not None: first, left = self.left.tree_to_list() left.right = self self.left = left else: first = self if self.right is not None: right, last = self.right.tree_to_list() right.left = self self.right = right else: last = self first.left = last last.right = first return first, last

pklausler 9y ago

The reversed problem is more interesting: given a doubly-linked sorted list (and its length), convert it to a balanced binary search tree.

sigjuice 9y ago
https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-16.html#%_thm_2.64 https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-16.htm...
cbarrick 9y ago
That's the DSW algorithm. https://en.wikipedia.org/wiki/Day-Stout-Warren_algorithm https://en.wikipedia.org/wiki/Day-Stout-Warren_algorithm
- nine_k 9y ago
  Pretty trivial, since you can easily find the middle of a doubly-linked list and step back. Then you simply do "find middle, use it as root, recursively build two subtrees". With a singly-linked list, it's much harder; I don't know (without googling) if a more efficient than "build and rebalance as you go" algorithm exists.
  - pklausler 9y ago
    If you know the length of the initial list (and that's obviously possible in O(N)), it's all easy.
  - tzs 9y ago
    You could convert a singly-linked list to a doubly-linked list in O(n), and then apply your favorite doubly-linked solution. You could even do this in place without increasing the size of each node at the cost of doubling the size of variables that point to nodes and slightly lowing down stepping through the list. You do this by storing the next and previous pointers for each node in the same location, xor'ed together. That doubles the size of variables that point to nodes and slows down stepping because you have to turn them into structs that store both a pointer to the node and a pointer to an adjacent node and update both of these pointers as you move through the list.

zmonx 9y ago

The declarative programming language Prolog is very suitable for reasoning about trees, lists and recursive structures in general. For example, here is a Prolog definition of the tree from the article: tree(node(4, node(2, node(1,nil,nil), node(3,nil,nil)), node(5,nil,nil))). I am using terms of the form nil/0 and node/3 to represent the tree. Let us start by converting the tree to a list. As requested, we shall consider the in-order traversal of the tree elements, described as a list. For such situations, Prolog DCG notation is very convenient, since it easily allows us to describe a list in relation to other terms (in this case, a tree): tree_to_list(nil) --> []. tree_to_list(node(E,Left,Right)) --> tree_to_list(Left), [E], tree_to_list(Right). Here is a sample query and its result: ?- tree(T), phrase(tree_to_list(T), Ls). T = node(4, ...), Ls = [1, 2, 3, 4, 5]. OK, so we now have the in-order traversal. Of course, lists are already implicitly "linked" in Prolog in one direction: Given a list, we can readily reason about the first element and the remaining elements. The task requires us to do more, i.e., reason about the reverse direction as well. One way to express this is to use rational trees, also known as cyclic terms in Prolog. For example, here is a case of cyclic term: ?- append([a,b,c], Ls, Ls). Ls = [a, b, c|Ls]. Here, Ls represents the circular list [a,b,c,a,b,c,a,...]. We can use this feature to our advantage as follows: list_with_backlinks([], []). list_with_backlinks([L|Ls0], [L-Prev|Ls]) :- append([L|Ls], Cs, Cs), foldl(with_backlink, Ls0, Ls, Cs, Prev). with_backlink(E, E-Cs0, Cs0, Cs) :- Cs0 = [_|Cs]. Sample query and answer: ?- list_with_backlinks([a,b,c], Cs). Cs = [a-[_S2|_S1], b-_S1, _S2], % where _S1 = [a, b-_S1, _S2|_S1], _S2 = c-[b-_S1, _S2|_S1] . Thus, as desired, we can generate a doubly-linked list from the original tree: ?- tree(T), phrase(tree_to_list(T), Ls0), list_with_backlinks(Ls0, Ls). T = node(4, ...), Ls0 = [1, 2, 3, 4, 5], Ls = [1-[_S4|_S1], 2-_S1, _S2, _S3, _S4], % where _S1 = [1, 2-_S1, _S2, _S3, _S4|_S1], _S2 = 3-[2-_S1, _S2, _S3, _S4|_S1], _S3 = 4-[_S2, _S3, _S4|_S1], _S4 = 5-[_S3, _S4|_S1] . Of course, this does not completely solve the task, which requires in-place modifications of the original tree. Pure Prolog lacks destructive modifications, so we cannot fully translate the code to Prolog. On the plus side, no pointers at all were necessary, and the recursions are pretty straight-forward.

atilimcetin 9y ago

This is one of the problems in 'Elements of Programming Interviews' book. - Convert a sorted doubly linked list into a BST C++: http://elementsofprogramminginterviews.com/solutions/cpp/sorted_list_to_bst.cc http://elementsofprogramminginterviews.com/solutions/cpp/sor... Java: http://elementsofprogramminginterviews.com/solutions/java/SortedListToBST.java http://elementsofprogramminginterviews.com/solutions/java/So... Python: http://elementsofprogramminginterviews.com/solutions/python/sorted_list_to_bst.py http://elementsofprogramminginterviews.com/solutions/python/... - Convert a BST to a sorted doubly linked list C++: http://elementsofprogramminginterviews.com/solutions/cpp/bst_to_sorted_doubly_list.cc http://elementsofprogramminginterviews.com/solutions/cpp/bst... Java: http://elementsofprogramminginterviews.com/solutions/java/BSTToSortedDoublyList.java http://elementsofprogramminginterviews.com/solutions/java/BS... Python: http://elementsofprogramminginterviews.com/solutions/python/bst_to_sorted_doubly_list.py http://elementsofprogramminginterviews.com/solutions/python/...

kazinator 9y ago

Here is a C library I wrote in 1999 which can convert, in-place, a container between Red-Black, AVL and linked list: http://www.kylheku.com/~kaz/austin.html http://www.kylheku.com/~kaz/austin.html