Monday, June 17, 2013

The Great Tree List Recursion Problem

Reference: http://cslibrary.stanford.edu/109/TreeListRecursion.html

Tree structure allows extensive use of recursion for performing various operations. This property of trees is exploited for converting a given BST into a circular doubly linked list.

Algorithm:

  1. Convert left subtree of the tree into a circular doubly linked list.
  2. Convert right subtree of the tree into a circular doubly linked list.
  3. Append root to the list of left subtree.
  4. Append the list of right subtree to the root.


1 comment: