How do you walk a BSP without recursion?..

quote:

---

Original post by monkeyman
It's a real shame that msn@glue.umd.edu sounds like such a dick, otherwise I'd probably ask him directly..

---

    

struct Node
{
    Node* left;
    Node* right;
    T data;
};

void WalkInorder( Node* root )
{
    Node* stack[]; //allocate this however you want.

    Node* iter = stack;
    *iter++ = 0;

    Node* curr = root;

    while( curr )
    {
        while( curr )
        {
            *iter++ = curr;
            curr = curr->left;
        }

        if( *--iter )
        {
            ProcessNode( *iter );

            curr = *iter->right;
        }
    }
};

  

quote:

---

Original post by felisandria
To be honest I kind of thought the whole point of using recursion is that if you can manage to get it working it''s the fastest, most elegant, and shortest (code-length-wise) way of doing whatever it is you''re trying to do.

---

quote:

---

I''d be curious too if someone could come up with a traversal of a binary tree not using recursion that somehow buys you something. Can''t really imagine what it would buy you to be honest, since it would probably have to be rather long, and you''re going to have to visit every node regardless so it wouldn''t speed it up any probably. It probably couldn''t be more efficient, because it''s really efficient to do recursion on BSP trees due to the fact that you''re actually technically queueing the information you''re reading but you''re queueing it on the stack itself in the form of information held in temporarily paused functions, and I can''t imagine coming up with anything more efficient than that.

-fel

---

$sp = $sp - 12 // stack stuff
$sp[12] = $s0
$sp[8]  = $s1
$sp[4]  = $ra
$s0 = $a0
$s1 = $a1
$t0 = $a0[0]  // node->left
bez $t0, skip1 // if node->left traverse left
  $a0 = $t0
  jal SELF  // recurse on left
skip1:
$a0 = $s0
jal $s1     // perform function
$a0 = $s0[4]  // node->right
bez $a0, skip2 // if node->right traverse right
  $a1 = $s1
  jal SELF  // recurse on right
skip2:
$ra = $sp[4]
$s0 = $sp[12]
$s1 = $so[8]
$sp = $sp + 12
jre $ra
 

$sp = $sp - 16
$sp[16] = $s0 // store $s vars
$sp[12] = $s3
$sp[8] = $ra  // store return address
$sp[4] = 0    // install sentinal
$s0 = $a1  // fp
$s3 = $a0  // node address
bez $s3, return
outer:
  $sp[0] = $s3  // push current node on stack
  $sp = $sp - 4
  $s3 = $s3[0]  // current node = node->left
  bnez $s3, outer  // repeat while not zero
inner:
  $sp = $sp + 4 // pop node from stack
  $s3 = $sp[0]
  bez $s3, return // reached sentinal, so return
  $a0 = $s3  // process node
  jal $s0
  $s3 = $s3[4] // current node = node->right
  bnez $s3, outer
  b inner
return:
$ra = $sp[4]
$s0 = $sp[12]
$s3 = $sp[8]
$sp = $sp - 12
jre $ra
 

quote:

---

Original post by Stoffel

We had a fairly lengthy discussion of this in a thread about a month back. I was strongly fighting for the side of recursion. Well, a lot of code flew around, and it turns out that for a lot of recursive problems, the non-recursive solution executes faster. Calls to recursive functions do take some time. I think if one were to implement an inline stack, one could probably get some performance gain. It would have to be profiled experimentally, but that was the outcome of the discussion. I was pretty disappointed, since recursion is so elegant & nifty. Oh well.

---

quote:

---

Avoid recursive functions due to the danger of overflowing the return address stack. Convert end-recursive functions to iterative code.

When the 12 entry return-address stack gets out of
synchronization, the latency of returns increase. The return-address stack becomes out of sync when:
- calls and returns do not match
- the depth of the return-address stack is exceeded because
of too many levels of nested functions calls

---

quote:

---

In order to program any [unthreaded] binary tree traversal without explicit recursion (not just a BSP), you need to manually maintain a stack

---

quote:

---

[MSCV optimizes] tail recursion into a simple loop.

---

quote:

---

Original post by Magmai Kai Holmlor
Thread the BSP tree.
Use the Next pointer (threaded trees do !).

Good luck, dynamic tree threading is hard. I mean hard .
Look up Threaded AVL trees for some pointers...

no stacks, no recurrsion; just another 4bytes a node and a lot of programmer''s grease.

Have none of you never heard of threaded trees!? Or am I on acid, and dreaming of something that doesn''t exist?

...
In order to program any [unthreaded] binary tree traversal without explicit recursion (not just a BSP), you need to manually maintain a stack

---

quote:

---

------------
[MSCV optimizes] tail recursion into a simple loop.
------------
Using the stack as a non-recursive stack implementation? or how? You mentioned this before, I''m just curious how it does it...

---

class Node {
  public:
    Node * left;
    Node * right;
    int data;
};

void Traverse(Node * root) {
  if (root == NULL) return;
  Traverse(root->left);
  printf("%d\n", root->data);
  Traverse(root->right);
}
 

_root$ = 8
?Traverse@@YAXPAVNode@@@Z PROC NEAR			; Traverse
; File node.cpp
; Line 10
	push	esi
; Line 11
	mov	esi, DWORD PTR _root$[esp]
	test	esi, esi
	je	SHORT $L551
$L548:
; Line 12
	mov	eax, DWORD PTR [esi]
	push	eax
	call	?Traverse@@YAXPAVNode@@@Z		; Traverse
; Line 13
	mov	ecx, DWORD PTR [esi+8]
	push	ecx
	push	OFFSET FLAT:$SG539
	call	_printf
; Line 14
	mov	esi, DWORD PTR [esi+4]
	add	esp, 12					; 0000000cH
	test	esi, esi
	jne	SHORT $L548
$L551:
	pop	esi
; Line 15
	ret	0
?Traverse@@YAXPAVNode@@@Z ENDP				; Traverse
 

quote:

---

Doesn''t a bsp''s do most of its work by virtual of the transversal? ie little work to do when visiting a node, it''s either in or out, next node?

---

quote:

---

Original post by monkeyman
Gee, you don''t sound like such a dick after all

---