CODEWITHSUNDEEP
cstackbinary-tree
kevin gomes
kevin gomes

Reputation: 1815

Benefit of threaded binary tree

In the documentation of threaded binary tree, I read

Both the recursive and non-recursive procedures for binary tree traversal require that pointers to all of the free nodes be kept temporarily on stack. This can be avoided by using threaded binary tree

My question is

1- How and when the pointers are kept in stack in Normal Binary Tree?

2- How the pointers are not added in stack in Threaded Binary Tree?

Upvotes: 1

Views: 232

Answers (1)

Andrew C
Andrew C

Reputation: 14863

1) They are talking about walking the tree. You either use a recusrive algorithm (which uses the CPU stack to keep track of things for you), or you use an iterative approach and keep a data structure stack and manage the nodes you need to visit yourself. The latter may perform better because you eliminate the overhead of the function calls, but it is often more conceptually difficult to understand.

2) A threaded tree keeps stores the information of how to walk the tree in the tree itself (instead of NULL pointers that you have to backtrack they point to the next location in the tree to walk), this allows you to walk the tree "in a straight line", so no stack is needed.

The wiki page does a pretty good job of showing this.

-A

Upvotes: 3

Related Questions