Showing posts with label Tree List Recursion Problem. Show all posts
Showing posts with label Tree List Recursion Problem. Show all posts

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.