CareerCup

If all you are doing is building a list of the tree, then just do any recursive traversal and add each node to the list as you go.

//inorder traverse using recursion.
//return list header
//t is the list tail
//r is the tree root
Node* Flat(Node* r, Node ** t)
{
    Node *h = null;

    // handle left tree, set list header.
    if(r->left == null)
    {
        h = r;
    }
    else
    {
        Node *leftTail = null;
        h = Flat(r->left, &leftTail);
        leftTail->right = r;   
    }

    // handle right tree
    if(r->right == null)
    {
        *t = r;
    }
    else
    {
        Node *rightListTail = null;
        r->right = Flat (r->right, &rightListTail);
    }
 
    // return header
    return h;
}

Node* MainFunc(Node* r)
{
    if(r==null) return null;

    Node* tail=null;
    return Flat(r, &tail);
}

I think it is better to flatten the binary tree using Pre Order traversal only. The point of flattening is to be able to un-flatten it at a future point of time.

If you flatten it using Inorder or Postorder, you would have difficulty finding out the root of the Tree from the list. But you wouldn't have that problem if the list is in Pre Order.

Try implementing the following recursively:

Flatten(Tree * root, Tree ** head, Tree ** tail);

This is just a general idea.

function buildLinkedList(Node parent)
{
Nodes headTailLeft=buildLinkedList(parent.left);
Nodes headTailRight=buildLinkedList(parent.right);
headTailLeft.tail.next=head;
head.next=headTailRight.head;
return headTailLeft.head;
}

I'm assuming they want an ordered link list or something, not a randomly linked list
just do an inorder traversal (left, add to list, right).

might look something like this

void buildlist(Node current){

if (current-> left != NULL){
buildlist(current->left);
}

addtotail(current); //assume this is a function that will add the node/value to the list, and maintains a pointer to the tail of the linked list.

if(current -> right != NULL){
buildlist(current->right);
}


}

void add(struct linknode** head,int data)
{
struct linknode*temp =NULL,*temp1;
if(*head==NULL)
{
(*head)=(struct linknode*)malloc(sizeof(struct linknode));
(*head)->data=data;
(*head)->next=NULL;
}
else
{
temp=*head;

while(temp->next!=NULL)
temp=temp->next;
temp1=(struct linknode*)malloc(sizeof(struct linknode));
temp1->data=data;
temp1->next=NULL;
temp->next=temp1;
}


}

void tree2link(struct treenode* root)
{
if(root==NULL)
return;
else
{
tree2link(root->left);
add(&head,root->data);
tree2link(root->right);
}

}

if we want to change the tree itself


void add(struct treenode* root)
{
struct treenode *temp=NULL;

if(head1==NULL)
{
head1=root;
head1->left==NULL;
head1->right==NULL;
}
else
{
temp=head1;
while(temp->left!=NULL)
temp=temp->left;

temp->left=root;
root->left=NULL;
root->right=NULL;
}
}

void tree2link(struct treenode* root)
{
if(root==NULL)
return;
else
{
tree2link(root->left);
tree2link(root->right);
add(root);
}

}

Do level wise traversal, just put the left or child to end of queue if they exits. After that dequeue a new element ,if its the root this will the first node of the link list or its an ordinary node add it to end of the link list .Again call the recursive function with recently dequeued element.

private static <T> DoublyLinkedList<T> flatten(BinaryTreeNode<T> btn) {

DoublyLinkedList<T> dll = new DoublyLinkedList<T>();

if(btn != null) {

dll.append(flatten(btn.getLeftChild()));
dll.add(btn.getValue());
dll.append(flatten(btn.getRightChild()));
}

return dll;
}


Is this solution correct?? what about the "tree can be modified" clause
...

public static LinkedListNode My_BinaryTree_to_LinkedList(BinaryTreeNode head){
if(head==null){
return null;
}
if(head.leftchild==null&&head.rightchild==null){
return new LinkedListNode(head.value);
}
LinkedListNode left=My_BinaryTree_to_LinkedList(head.leftchild);
LinkedListNode right=My_BinaryTree_to_LinkedList(head.rightchild);
LinkedListNode newhead=new LinkedListNode(head.value);
if(left==null){
newhead.next=right;
return newhead;
}
if(right==null){
newhead.next=left;
return newhead;
}
LinkedListNode current=left;
while(current.next!=null){
current=current.next;
}
current.next=right;
newhead.next=left;
return newhead;
}

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
typedef struct btree
{
struct btree *left;
int data;
struct btree *right;
}btree;

void create(btree *tree1)
{
btree *temp;
int val,choice;
printf("\ndo this have a left childnode of %d?1 or 0\n",tree1->data);
scanf("%d",&choice);
if(choice==1)
{
temp=(btree*)malloc(sizeof(btree));
printf("enter data\n");
scanf("%d",&val);
temp->data=val;
tree1->left=temp;
create(temp);
}
else
tree1->left=NULL;
printf("do this have a right child node of %d?1 or 0\n",tree1->data);
scanf("%d",&choice);
if(choice==1)
{
temp=(btree*)malloc(sizeof(btree));
printf("enter data\n");
scanf("%d",&val);
temp->data=val;
tree1->right=temp;
create(temp);
}
else
tree1->right=NULL;
}
btree* convert(btree *root,btree **head)
{
static int i;
btree * start;
if(root!=NULL)
{
if(*head==NULL)
{
*head=root;
start=root;
}
else
{
(*head)->left=root;
(*head)=(*head)->left;

}
convert(root->left,head);
convert(root->right,head);
return start;
}
else
return NULL;
}
void traverse(btree *head)
{
btree *p;
p=head;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->left;
}
}

main()
{
btree *tree1,*start;
int val;
tree1=(btree*)malloc(sizeof(btree));
if(tree1!=NULL)
{
printf("enter data of root node\n");
scanf("%d",&val);
tree1->data=val;
create(tree1);
}
btree * head;
head=NULL;
head=convert(tree1,&head);
traverse(head);
getch();
}

To create array that represent BST I'd do pre-order traversal. For missing leaves I'd output NULL to array so I know when to stop when I recreate tree back from array.