Do we have stack involvement in a threaded tree?

[zak100]

Homework Statement

In the book it gives following background for using threaded trees:
"The concern is that some additional time has to be spent to maintain the stack & some more space has to be set aside for the stack itself."
& then it says
"It is more efficient to incorporate the stack as part of the tree. This is done by incorporating threads in a given node"

From first sentence "It is more efficient to incorporate the stack as part of the tree" it looks as if stack is utilized in the threaded tree but i can't understand what it means " incorporate stack as part of tree" but in the next sentence it says "This is done by incorporating threads in a given node". By threads we mean pointers which point to the inorder successor & inoder predecessor. They are not stack. So this is my problem that i can't understand whether stack is used in a threaded tree or not

Homework Equations

No equations, only theory.

The Attempt at a Solution

I think stack is present but at the same time it has threads/pointers also which help in efficient traversal

Some body please guide me.

Zulfi.

 

[Wee-Lamm]

The article is suggesting that the 2 pointers already associated with each node, can negate the need for a stack in that we can change the direction we expect them to point.

Presume that each node would have 2 children designated as node.left and node.right. Typically, we would use a stack to retain reference to the parent node and which child node is next to be referenced, and the stack must be large enough to travel from the Root node to the bottom node of the branch with the most generations, as well as sibling nodes that have been visited in neighboring sub-branches.

In this scenario though, we can include an additional data field to indicate whether the pointers should thread to either of the child nodes, or thread to successor (child) and predecessor(parent) nodes. In short, each node incorporates it's own psuedo-stack, using itself as the reference point.

 

[zak100]

Hi,
Thanks for your response but i feel that you are trying to avoid my question.

I can't understand whether we have stack or not in a threaded tree from your reply.
i got following from a site:
"
In many applications, binary tree traversals are carried out repeatedly, and the overhead of stack operations - the implicit ones carried out by the runtime system (when a recursively coded traversal is being executed), or the explicit pushes/pops of a non-recursive (but stack-driven) traversal procedure - is costly in terms of program execution time. (The traversal isO(n) in terms of computational effort, but the stack operations introduce overhead (a larger run-time constant) than might be desirable.) It is sometimes useful to modify the data structure (of pointers and nodes) which represents the binary tree so as to speed up - say - the inorder traversal process: make it "stack-free".
http://www.cs.rutgers.edu/~kaplan/503/handouts/threadedtrees.html

So can i say that we don't have stack involvement in a threaded tree?
Some body please provide me unambiguous answer to my question.

Zulfi.

 

[Wee-Lamm]

Hi,
Thanks for your response but i feel that you are trying to avoid my question.

I can't understand whether we have stack or not in a threaded tree from your reply.
i got following from a site:
"
In many applications, binary tree traversals are carried out repeatedly, and the overhead of stack operations - the implicit ones carried out by the runtime system (when a recursively coded traversal is being executed), or the explicit pushes/pops of a non-recursive (but stack-driven) traversal procedure - is costly in terms of program execution time. (The traversal isO(n) in terms of computational effort, but the stack operations introduce overhead (a larger run-time constant) than might be desirable.) It is sometimes useful to modify the data structure (of pointers and nodes) which represents the binary tree so as to speed up - say - the inorder traversal process: make it "stack-free".
http://www.cs.rutgers.edu/~kaplan/503/handouts/threadedtrees.html

So can i say that we don't have stack involvement in a threaded tree?
Some body please provide me unambiguous answer to my question.

Zulfi.

Short answer, No there is not a stack 'object' in addition to the tree 'object' in the example above.

In a Binary tree, each node has 2 children and includes a pointer to each one. A stack would normally be implemented to track the path of which nodes were visited prior to the current one, so traversal lands on the correct parent node.

In the scenario above, the pointers can be toggled to point to the next child to be visited and the parent, rather than the left and right children. Where the 2nd pointer already points to the parent, it is not necessary to push that pointer to a stack to preserve the path.

 

[rcgldr]

In the scenario above, the pointers can be toggled to point to the next child to be visited and the parent, rather than the left and right children.

What I get when I read that article is that pointers are not toggled unless a new node is inserted to the tree. The threaded tree implementation is accomplished by adding two booleans to each node, and by using a dummy node as the head node for the tree.

Getting back to the OP's question, the functions used to traverse the threaded tree are iterative and not recursive, so only a fixed amount of stack is used by each function regardless of tree depth, and in the case of a processor where parameters, return address, return value, are in registers, then no stack would be needed.

Rebalancing a tree would probably require recursion.

The article mentions right threaded trees with no left nodes, isn't this the equivalent of a linked list?