Given a binary tree (with left and right child only), how do you write a recursive function to make it into a simple linked list in-place? (no new data structure should be created. Pseudo code is ok). Suppose each node has an integer value, like 123, or 2, or 3. The final link list should have all the nodes in the tree. The order is not important.
Update: needs to be in-place. no new data structure should be created.
You are really asking how do I walk a binary tree. The answer can be found in any book on algorithms and data structures.
There are always different ways to iterate over a tree, as there are:
You can choose either of them to form your list...
For example (pseudocode, PreOrder):
function treeToList(LinkedList l, Tree t)
if(t not nil)
l.add(t.element)
treeToList(l, t.Left)
treeToList(l, t.Right)
endif
end function
Remenber: If you perfomed an InOrder on a binary search tree you would get the elements in sorted order.
Not to be rude, but this sounds a bit like homework. Let me give a description as an answer:
You create an empty linked list for the result.
Make a help function which takes a linked list and a node.
The helper function should add the child nodes (if any) to the list and call itself recursively on the child nodes (if any).
Add the root node to the result list.
Call the helper function on the root node and the result list.
Return the result list to the caller.
There are of course a lot about this on Wikipedia: binary trees and tree traversal.
Edit: or look at the pseudo-code posted by Kevin :-)
You can "walk a tree" in many orders, the main ones being pre-, post-, and in-order. Here's some pseudocode for in-order, for example:
def in_walk(tree, doit):
if tree is null: return
in_walk(tree.left, doit)
doit(tree.root)
in_walk(tree.right, doit)
I hope the assumptions in this pseudocode are obvious: a tree has left and right links, which can be null meaning "nothing more to walk here", and a root node; you can pass a function or closure that does the right think (append to a linked list or whatever) given a node argument.
/* bst.c: sort the input numbers and print them forward and backward with no duplicates */
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node *left;
struct node *right;
};
static struct node **bst_find(struct node **root, int key) {
struct node **n;
n = root;
while (*n != NULL && (*n)->key != key) {
if (key < (*n)->key) {
n = &(*n)->left;
} else {
n = &(*n)->right;
}
}
return n;
}
static void bst_insert(struct node **root, int key) {
struct node **n;
n = bst_find(root, key);
if (*n == NULL) {
*n = malloc(sizeof (**n));
(*n)->key = key;
(*n)->left = NULL;
(*n)->right = NULL;
}
}
/* massage the tree rooted at "root" to be a doubly-linked list
* return the leftmost and rightmost nodes via the parameters "leftend" and "rightend"
* bst_flatten() is invoked 2N+1 times, where N is the number of tree elements
*/
static long Flatten_count = 0;
static void bst_flatten(struct node **leftend, struct node **rightend, struct node *root) {
Flatten_count++;
if (root != NULL) {
/* flatten the left side of the tree */
*leftend = root;
bst_flatten(leftend, &root->left, root->left);
/* if necessary, splice "root" onto the right end */
if (root->left != NULL) {
root->left->right = root;
}
/* flatten the right side of the tree */
*rightend = root;
bst_flatten(&root->right, rightend, root->right);
/* if necessary, splice "root" onto the left end */
if (root->right != NULL) {
root->right->left = root;
}
}
}
int main(void) {
int key;
long N = 0;
struct node *root = NULL;
struct node *leftend = NULL;
struct node *rightend = NULL;
struct node *n;
/* read the input into a bst */
while (scanf("%d", &key) == 1) {
N++;
bst_insert(&root, key);
}
/* make a list */
bst_flatten(&leftend, &rightend, root);
/* traverse the list forward */
for (n = leftend; n != NULL; n = n->right) {
printf("%d\n", n->key);
}
/* traverse the list backward */
for (n = rightend; n != NULL; n = n->left) {
printf("%d\n", n->key);
}
fprintf(stderr, "%ld items input, %ld invocations of bst_flatten()\n", N, Flatten_count);
return 0;
}
Since you've tagged it as homework, I'll reply without source code or pseudo code, but with a more all-round description.
Since your tree will contain all the values you want to contain in the linked list, we have to make sure we reach them all.
To do that, we'll have to make sure we process every leaf node.
To do that, we need to make sure we process every left and right child of every node.
Let's start with the root node, which is generally the one you have a reference to when you're talking about a binary tree.
I'm assuming you know how to produce a linked list by sequentially appending items to it.
So to process the root node, we do this:
That takes care of the single value that can optionally be stored in the root node. Some binary trees only store values in leaf nodes (nodes without children), most store values also in internal nodes (nodes with children).
But that will of course get us nowhere, since we only add one item, and we don't even know where in all the values this specific value is, so it could be the first, or the last, or any in between.
But, we know that if the root node has children in the left "direction", then any values we might find in all those nodes will come before the node in the root node.
And we also know that if the root node has children in the right "direction", those values will come after it.
So what we can do is this:
This approach assumes that:
If you define the above approach as a method, you'll have something like this:
to process a node, do this:
first process the left-child sub-node, if present
then append the value of the node, if any
then process the right-child sub-node, if present
In the above pseudo-code, where you see the word "process", you apply the same process to those nodes as described above.
Here's the C# code to process a simple binary tree and append the result to a given linked list:
public void AppendTreeToLinkedList<T>(Node<T> node, LinkedList<T> list)
{
if (node.LeftChild != null)
AppendTreeToLinkedList(node.LeftChild, list);
list.Append(node.Value);
if (node.RightChild != null)
AppendTreeToLinkedList(node.RightChild, list);
}
Assume the tree has nodes containing pointers to nodes called left and right. We'll end up with a list using only the right node pointers.
listify( node )
if node has no children
return
else if node.left == null
listify(node.right)
else if node.right == null
listify(node.left)
mode.right = node.left
else
listify(node.left)
listify(node.right)
temp = node.left
while temp.right != null
temp = temp.right
temp.right = node.right
node.right = node.left
To get a doubly-liked list that is sorted in the same way as the original tree, C# code:
function Listify(Node n, out Node First, out Node Last)
{
if ( Node.Left != null )
{
Node Tmp;
Listify(Node.Left, out First, out Tmp);
Node.Left = Tmp;
}
else
{
First = Node;
}
if ( Node.Right != null )
{
Node Tmp;
Listify(Node.Right, out Tmp, out Last);
Node.Right = Tmp;
}
else
{
Last = Node;
}
}
In Scheme, using memoized recursion, an in-order algorithm would be:
(define (tree->list tree)
(define empty-set (list))
(define (copy-to-list tree result-list)
(if (null? tree)
result-list
(copy-to-list (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch tree)
result-list)))))
(copy-to-list tree empty-set))
This assumes that a tree structure is represented as:
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
(list entry left right))
N.B. I could have used the literal '() for the empty-set but SO messes up the color coding of the block quoted code.