Great Tree Recursion Program

Question

I ran into an interesting problem called the Big Tree List Problem. The problem is this:

In an ordered binary tree, each node contains one data element and “small” and “large” pointers to subtrees. All nodes in the "small" subtree are less than or equal to the data in the parent node. All nodes in the "large" subtree are larger than the parent node. And the circular double list consists of the previous and next pointers.

The task is to take an ordered binary tree and rearrange the internal pointers to make a circular double-linked list from it. The "small" pointer should play the role of "previous", and the "big" pointer should play the role of "next". The list should be organized so that the nodes are in ascending order. I have to write a recursive function and return a pointer to a new list.

The operation must be performed in O (n) time.

I understand that recursion will go through the tree, but how to change small and large subtrees to lists recursively, I also need to add these lists along with the parent node.

How can I approach the problem? .. I just need a guide to solve the problem!

Answer 1

The idea is to create a method that converts a node tree containing subtrees (child nodes) into a loop. And given the node that transformed the children (for example, after returning the recursive calls), you create a new loop by pointing the large pointer (next) from the largest node to the smallest node, and the small pointer to the smallest node to the largest node.

It 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) 

Answer 2

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

So, you already have a recLink(Tree t) function that takes a pointer to a tree, it turns out that the tree is in a doubly connected ring list and returns a pointer to the head of the list (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 working with edges (empty child branches, etc.). :)

Answer 3

if you have a simple tree of 3 nodes

 B <--- A ---> C 

walk along the left and right sides, find the pointers for each node, then

 B -> C B <- C 

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