The Great Tree list recursion program

4
votes

I faced an interesting problem called as the Great Tree-List Problem. The Problem is as follows :

In the ordered binary tree, each node contains a single data element and "small" and "large" pointers to sub-trees .All the nodes in the "small" sub-tree are less than or equal to the data in the parent node. All the nodes in the "large" sub-tree are greater than the parent node. And a circular doubly linked list consist of previous and next pointers.

The problem is to take an ordered binary tree and rearrange the internal pointers to make a circular doubly linked list out of it. The "small" pointer should play the role of "previous" and the "large" pointer should play the role of "next". The list should be arranged so that the nodes are in increasing order. I have to write a recursive function & Return the head pointer to the new list.

The operation should be done in O(n) time.

I understand that recursion will go down the tree, but how to recursively change the small and large sub-trees into lists, also i have to append those lists together with the parent node.

How should i approach the problem?.. I just need a direction to solve the problem!.

3
algorithmpointersrecursiontreecircular-list
so the "ordered binary tree" is almost like a BST? – Fallen
A recursive in-order traversal should work just fine. Just be sure to store the pointer to the right sub-tree before visiting (modifying) the node itself. I guess this would be O(n) but memory footprint could get pretty bad. (especially if you're using a limited stack) – user645280
Solution here: cslibrary.stanford.edu/109/TreeListRecursion.html – Tarik

3 Answers

5
votes

The idea is to create a method that converts a tree node containing subtrees (children nodes) into a loop. And given a node that has converted children (e.g. after recursive calls came back), you create a new loop by pointing the large pointer (next) of the largest node to the smallest node, and the small pointer of the smallest node to the largest node.

May not be complete, but it will be close to this:

tree_node {
    small
    large
}

convert(node){
    //base case 1, if leaf node
    if node.small == null && node.large == null
        return (self, self)

    //recursively convert children
    if node.small !=null
        smallest, larger = convert(node.small)
    else
        smallest = larger = self

    if node.large !=null
        smaller, largest = convert(node.large)
    else
        smaller = largest = self

    //wrap the ends of the chain
    largest.large = smallest
    smallest.small = largest
    //wrap the mid part
    smaller.small = larger
    larger.large = small

    //return pointers to the absolute smallest and largest of this subtree
    return (smallest, largest)
}

//actually doing it 
convert(tree.root)
2
votes

The key to recursive programming is to imagine you already have the solution.

So, you already have a function recLink(Tree t) which receives a pointer to a tree, turns that tree into a doubly-linked circular list and returns a pointer to the list's head (leftmost) node:

recLink( n={Node: left, elt, right}) =  // pattern match tree to a full node
  rt := recLink( right);                // already
  lt := recLink( left);                 //   have it
  n.right := rt;       n.left := lt.left;        // middle node
  lt.left.right := n;  rt.left.right := lt;      // right edges
  lt.left := rt.left;  rt.left := n;      
  return lt;

Finish up with the edge cases (empty child branches etc.). :)

1
votes

assuming you have a simple tree of 3 nodes 

B <--- A ---> C

walk down the left and right sides, get the pointers for each node, then have 

B -> C
B <- C

Since your tree is binary, it will be composed of 3 node "subtrees" that can recursively use this strategy.