0

Suppose you want to write a simple math reducer that will, for example, do the transformation:

((add ((add 2) 3)) ((add 4) 2)) -> 11

A simple algorithm could be (example in JavaScript):

function r(a){
    if (typeof(a)!=="object") return a;
    var a = [r(a[0]), r(a[1])];
    return a[0][0]==="add" ? a[0][1] + a[1] : a;
}
console.assert(r([["add",[["add",2],3]],[["add",4],2]]) === 11);

Is it possible to solve the same problem with constant stack?

Cœur
  • 37,241
  • 25
  • 195
  • 267
MaiaVictor
  • 51,090
  • 44
  • 144
  • 286
  • 2
    non-recursive ... recursive? – Simeon Visser Dec 25 '13 at 19:29
  • Bad wording, I'm still not sure how to title this. – MaiaVictor Dec 25 '13 at 19:30
  • I'm not sure what you're asking either. If it can't be recursive and it can't produce a stack then what exactly is allowed? You want to traverse a tree but it can't build a call stack? – Simeon Visser Dec 25 '13 at 19:32
  • I want to solve that problem without building a stack - which I guess is the same as saying that I want to transverse a binary tree without doing so (is it impossible?) – MaiaVictor Dec 25 '13 at 19:36
  • 1
    Yes, you can make *any* recursive program iterative by using a stack (data structure) on the heap. – Bernhard Barker Dec 25 '13 at 19:38
  • 3
    I guess OP asking if it possible to traverse tree bottom-up using only O(1) space. I guess, it's possible if you have direct pointers to tree leaves and nodes have pointers to their parents. What I'm not sure is if it possible to _build_ such tree using algo w/ O(1) space. – Victor Sorokin Dec 25 '13 at 19:39
  • @VictorSorokin I could use a specialized data-structure for that without problems - that is, no worries about the building phase - but your comment alone isn't enough for me to figure out what you mean. – MaiaVictor Dec 25 '13 at 19:47
  • 1
    @Viclib you just point a working pointer at the root, make a loop `while(not done){ ... }` and move a working pointer around, detecting the reducing condition, replacing nodes with values when you can, until `done`. – Will Ness Dec 25 '13 at 19:52

3 Answers3

1

Any recursive algorithm can be emulated using a stack on the heap and a loop. So, yes, it is possible to do this in a single function call.

If you are talking about traversing a single-linked tree in constant space (both stack and heap), then no, you cannot do that (you have to remember your way back up).

sds
  • 58,617
  • 29
  • 161
  • 278
  • I'm upvoting you, but I think the last statement is false - see Morris Inorder Tree Transversal. I'm just not sure how to adapt this algorithm to my problem. – MaiaVictor Dec 25 '13 at 21:02
  • 1
    @Viclib: "Morris Inorder Tree Transversal" adds _additional_ linking structure which is explicitly excluded by the wording "_single_-linked tree". – sds Dec 25 '13 at 21:07
1

If you transform your tree structure to zipper so you can traverse it using state machine. It is no longer simple tree but allows you make it non-recursive or tail recursive.

Hynek -Pichi- Vychodil
  • 26,174
  • 5
  • 52
  • 73
1

Yes, it's possible to do a depth-first traversal of a binary tree without using recursion, explicitly maintaining a stack, or modifying the tree nodes.

The resulting algorithm requires O(1) extra space and O(n^2) time.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351