CareerCup

This is just a simple question of converting a BST to a linked list (singly or doubly). You can find the answer to this by Googling online

Flatten( Tree root){
if(root == null)
return null;
else 
L = Flatten(root ->left);
R = Flatten(root-right);

root->right = R;
(last Node of L) -> Right = root;

return L;

void inorder(tree t)
{
if(t == NULL)
return;
inorder(t->left);
printf("%d ", t->val);
inorder(t->right);
}

flatten(node *ptr)
{
     if(ptr==null)return;

     node * alist=flatten(ptr->left);
     node *blist =flatten(ptr->right);
     node * tmp=alist;
     while(tmp->next!=null)tmp=tmp->next;
           tmp->next=ptr;
           tmp=ptr;
           tmp->next=blist;
           return alist;
           
}

this works correctly

is it a Doubly linked list ??
like left pointing to prev node and right pointing to next node ???

First Add all nodes in a queue in inorder.
Now go through the queue and assign right/left pointers on adjacent elements.
O(n) time

yes this is doubly link list.
I was asked to re arrange the existing tree.

hmm..
tis s my idea. (with one extra static variable pre) give ur suggestions..
do inorder traversal and store the first visiting node in variable pre.
now while visiting each node do the following
pre->right=current; // previous nodes next for first node (i.e pre=NULL) skip tis
current->left=pre; // current nodes previous
pre=current
will this work ???

I wanted to provide a solution that does not require any static variables outside of the recursion loop. That means you have to traverse the nodes to get to the last one before adding the next node, so it is definitely not more efficient than solutions using a static variable, but it is more self-contained.

public BinaryTreeNode FlattenInOrderTree(BinaryTreeNode currentNode)
        {
            BinaryTreeNode newNode = null;
            // Left
            if (currentNode.LeftChildNode != null) newNode = FlattenInOrderTree(currentNode.LeftChildNode);
            else return new BinaryTreeNode(currentNode.Value);
            // Middle
            BinaryTreeNode rightMostChildNode = newNode;
            while (rightMostChildNode.RightChildNode != null)
                rightMostChildNode = rightMostChildNode.RightChildNode;
            rightMostChildNode.RightChildNode = new BinaryTreeNode(currentNode.Value);
            rightMostChildNode.RightChildNode.ParentNode = rightMostChildNode;
            // Right
            if (currentNode.RightChildNode != null) rightMostChildNode.RightChildNode.RightChildNode = FlattenInOrderTree(currentNode.RightChildNode);
            rightMostChildNode.RightChildNode.RightChildNode.ParentNode = rightMostChildNode.RightChildNode;

            return newNode;
        }

Node* inorderList(Node* n)
{
    if(!n) return NULL;
    Node* l = inorderList(n->left);
    if(l) l->right = n;
    inorderList(n->right);
    return n;
}

If this is just a binary tree then we can add at the leaves. so, the complexity would be nothing but the addition of the second tree into the first tree.

If this is a bst, then we can add each of the nodes of the second bst into the first bst using the standard bst rules.

Node *flatten(Node *root)
{
if (root)
{
root = flatten(root->left);
if (root)
{
add_list(root);
root = flatten(root->right);
}
return NULL;
}

def flatten_util(self,root):
        if root:
            # if root.left == None and root.right == None:
            #     return root, root
    
            append = root
            x=root.right
            if root.left:
                left_ll, left_last = self.flatten_util(root.left)
                root.right = left_ll
                root.left = None
                append = left_last
            if x:
                right_ll, right_last = self.flatten_util(x)
                append.right = right_ll
                append.left = None
                append = right_last
            #print_ll(root)
            #print
            return root, append