performance question related to BST traversal

[subramanian100in]

This is not a homework assignment question.
Kindly excuse me for posting this question here.

Suppose a BST contains 100,000 ndoes.

Suppose I have to traverse the BST by Preorder, say, without using
recursion. Suppose I know the count of nodes. Suppose I use a stack
approach for traversal.

Implementation 1:
I allocate memory for an array of nodeCount times the size of a tree
node. Then I traverse the tree using this stack for pushing and
popping the nodes temporarily.

Advantage: malloc and free will be called only once.
DIsadvantage: huge memory will be needed, whose availability may not
be assured and even if available, all of it may not be needed.

Implementation 2:
Instead of an array of nodes, I use a singly linked list. Push and pop
in the beginning of the list each time.

Advantage: memory is allocated only on need based.
Disadvantage : frequent calls to malloc and free.

QUESTION: Kindly explain as to which approach should be preferred and
why ?
Is there any other way of traversing the tree without using recursion?

Thanks

 

[Richard Harter]

This is not a homework assignment question.
Kindly excuse me for posting this question here.

Suppose a BST contains 100,000 ndoes.

Suppose I have to traverse the BST by Preorder, say, without using
recursion. Suppose I know the count of nodes. Suppose I use a stack
approach for traversal.

Implementation 1:
I allocate memory for an array of nodeCount times the size of a tree
node. Then I traverse the tree using this stack for pushing and
popping the nodes temporarily.

Advantage: malloc and free will be called only once.
DIsadvantage: huge memory will be needed, whose availability may not
be assured and even if available, all of it may not be needed.

Implementation 2:
Instead of an array of nodes, I use a singly linked list. Push and pop
in the beginning of the list each time.

Advantage: memory is allocated only on need based.
Disadvantage : frequent calls to malloc and free.

QUESTION: Kindly explain as to which approach should be preferred and
why ?
Is there any other way of traversing the tree without using recursion?

Given your constraints you are going to have to grab some memory one way
or another. However the considerations you are running into are typical
issues in C and it is worth while reviewing common, useful strategies.

In implementation one, consider allocating a predetermined size for the
stack and doubling the size with realloc whenever the stack is about to
overflow. The number of calls to malloc/realloc will be O(log n). An
advantage of this approach is that there will only be one call to free.

In implementation two, consider allocating a number of nodes at once.
That is, allocate an array of nodes and link them into a free list.
When you push something on the stack you get its node from the free
list, and when you pop something from the stack you put the node back on
the free list. In this implementation you don't have to realloc. In
fact you had better not if you are using pointers. If the free list is
empty grab more space as before and link it into the free list.

In implementation two there is one thing you have to be careful about
and that is that you have to keep track of the arrays that you allocated
so that you can free them later. One way to do that is to reserve the
first node (index 0) as use as a linked list that links the arrays
together.

Again, you can double the size of each array allocation for O(log n)
allocations. However you can also allocate a fixed size array of nodes
each time. Which is more efficient depends on the implementation but it
probably doesn't matter.

HTH