Mumbai University > COMPS > Sem 3 > Data Structures

Marks: 10 M

Year: May 2014

• A tree is a set of nodes which have data and pointers or references. The pointers point to the children nodes of the node. The constraint is that no reference is duplicated and no node points to the root.
• A binary tree has nodes with number of children not exceeding two.
• 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. It is sometimes useful to modify the data structure (of pointers and records) which represents the binary tree so as to speed up - say - the inorder traversal process: make it "stack-free".
• A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists) , and all left child pointers that would normally be null point to the inorder predecessor of the node.

• There are two types of Threaded Binary Trees:-

  1. Single Threaded: each node is threaded towards either(right)' the in-order predecessor or' successor.
  2. Double threaded: each node is threaded towards both(left & right)' the in-order predecessor and' successor.

• Here is the algorithm for the tree traversal:-

  Start
  Go to the left-most node and print it.
  If the node’s right pointer is null, Go to step 7.
  Go to the node where the current node’s right pointer is pointing.
  Print the node.
  Go to step 3.
  Stop.
  

• Applying this algorithm to the above diagram of a treaded binary tree, we get the left-most node as 20. 20 is printed. Since the node’s right pointer is not null, we go there. The value is 30. Similarly, 45, 50, 55, 60 and 65 are printed. When we reach 65, we see that its right pointer is null. Hence we stop.

• The time complexity of traversal in a Threaded Binary Search Tree is O(n).