performance question related to BST traversal

Discussion in 'C Programming' started by subramanian100in@yahoo.com, India, Mar 26, 2007.

  1. , India

    , India Guest

    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
    , India, Mar 26, 2007
    #1
    1. Advertising

  2. On 26 Mar 2007 01:19:54 -0700, ", India"
    <> wrote:

    >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
    Richard Harter, Mar 26, 2007
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andrew Edwards

    BST & recursion

    Andrew Edwards, Jul 30, 2003, in forum: C++
    Replies:
    12
    Views:
    758
    Karl Heinz Buchegger
    Aug 4, 2003
  2. Rupert harrison

    BST

    Rupert harrison, Sep 15, 2003, in forum: C++
    Replies:
    2
    Views:
    541
    Karl Heinz Buchegger
    Sep 15, 2003
  3. Ridimz

    BST: remove less than

    Ridimz, Oct 4, 2003, in forum: C++
    Replies:
    8
    Views:
    516
    Josh Sebastian
    Oct 7, 2003
  4. Ice
    Replies:
    4
    Views:
    4,990
  5. puzzlecracker

    LL TO BST

    puzzlecracker, Jan 19, 2005, in forum: C++
    Replies:
    2
    Views:
    382
    Joseph Turian
    Jan 19, 2005
Loading...

Share This Page