CareerCup

just a variant question of converting it into singly linked list

class node{
public:
	int key;
	node* left;
	node* right;
	node(int key) {
		this->key = key;
		left = right = 0;
	}
};

node *degenerate(node *root) {
	if (!root) return 0;
	node *newroot = 0;
	for(newroot = root;newroot->left;newroot = newroot->left);
	convertToList(root);
	return newroot;
}

void convertToList(node *p) {
	node *leftHighest = 0;
	if (p->left) {
		for(leftHighest = p->left;leftHighest->right;leftHighest = leftHighest->right);
		convertToList(p->left);
		leftHighest->right = p;
		leftHighest->left = 0;
	}
	
	node *rightLowest = 0;
	if (p->right) {
		for(rightLowest = p->right;rightLowest->left;rightLowest = rightLowest->left);
		convertToList(p->right);
		p->right = rightLowest;
		p->left = 0;
	}
}

bT *head = NULL;
bT *tail = NULL;
bT *tmp = NULL;

addToList(bT *s)
{

if(head == NULL)
  {
    head=tail=s;
    s->left = s;
    return;
  }

//if node data greater than tail then insert at last pos
else if (s->data > tail->data) 
  {
    s->left = tail;
    tail->right = s;
    tail = s;
  } 

//if node data less than head then insert at fisrt pos
else if(s->data < head->data) 
  {
    s->right = head;
    head->left = s;
    s->left = s;
    head = s;; 
  } 

else  // else insert in between
  {
    tmp = head->right;
    while(tmp !=NULL)
    {
      if(tmp->data > s->data)
        {
          s->right = tmp;
          s->left = tmp->left;
          tmp->left->right = s;
          tmp->left = s;
          break;
        } // if
      tmp = tmp->right;
    } // while

  }//else
} //addToList


void treeToList(bT *s)
{
  if(NULL == s)     return;

  treeToList(s->left);
  addToList(s);
  treeToList(s->right);
}

recursive, degenerate left subtree,hook current root to it, root.'s right node is degenerated right subtree

the given tree is a BST,right?

the given tree is a BST,right?

public Node convertToLinkList() {
		convertToLinkList(mRoot);
		Node head = mRoot;
		while (head.mLeft != null) {
			head = head.mLeft;
		}
		return head;
	}

	Node last = null;

	public void convertToLinkList(Node root) {
		if (root == null) {
			return;
		}

		convertToLinkList(root.mLeft);
		root.mLeft = last;
		if (last != null) {
			last.mRight = root;
		}
		last = root;
		convertToLinkList(root.mRight);
	}

Why can't one just do an inorder_treewalk and convert into singly linked list?
- Add each TreeNode to head of the ListNode if descending sorted list is required, otherwise add to a Tail ListNode...

public Node degenerateTree(Node root){
		if(root!=null){
			Node newRoot = degenerateTree(root.left);
			Node node = degenerateTree(root.right);
			root.left = null;
			if(node!= null){
				root.right = node;
			}
			if(newRoot != null){
				Node focusNode = newRoot;
				while(true){
					if(focusNode.right == null){
						focusNode.right = root;
						return newRoot;
					}
					focusNode = focusNode.right;
				}
			}
		}
		return root;
	}

The below code creates and in order single linked list. You need to sort it.
The node "head" points to the start of the single linked list.
I initially create the double linked list and then remove the left links.

Node head = null;
boolean firstTime = true;

private Node createLinkedList(Node root) {
	// TODO Auto-generated method stub
		
	if( root == null) {
            return null;
        }
 
        if(root.left != null){
 
            Node leftTreeNode = createLinkedList(root.left);
 
            while(leftTreeNode.right != null){
                leftTreeNode = leftTreeNode.right;
            }
 
            leftTreeNode.right = (root);
        }
 
        if(firstTime && root.left == null) {
        	head = root;
        	firstTime = false;
        }
 
        if(root.right != null){
 
            Node rightTreeNode = createLinkedList(root.right);
 
            while(rightTreeNode.left != null){
                rightTreeNode = rightTreeNode.left;
            }
 
            root.right = (rightTreeNode);
        }
 
        return root;
}

private void removeLeftLinks() {
	Node temp = head;
	while(temp != null) {
		temp.left = null;
		temp = temp.right;
	}
}

This worked. i have tested it. If you find any issues in the code please let me know. I am yet to sort it though.

Algo
Remove min element from Btree and place it to the right of right most element;

Remove 2nd min element from BTree and place it to the right of right most element.

............ continue upto nth min element;

Complexity
O(n ^2) To remove min element in each iteration will take O(n).

code
This algo can be coded using recursion with some temp variables.

I think this question is just to transfer a given unbalanced BST to a double linked list.

/** 
 * Convert a tree to a linked list with left pointing to NULL, i.e use right for next pointer.
 * Does it in place.
 */
node_t *merge_lists(node_t *ll, node_t *root, node_t *lr)
{
    // get the rightOf(ll)
    node_t *llr = NULL;

    if (ll && ll->right)
        llr = ll->right;
    else if (ll) llr = ll;

    for (; llr && llr->right; llr = llr->right);

    // point rightOf(ll) to root
    if (llr) {
        llr->right = root;
    }

    // mark root's left as NULL
    root -> left = NULL;

    // points root's right to lr
    root -> right = lr;

    // return ll, the new list head.
    if (ll) return ll;

    // if left is NULL then our list head is root.
    return(root);
}

node_t * degen_tree(node_t *root)
{
    if (!root)
        return NULL; // base case.

    node_t *left_l = degen_tree(root->left);
    node_t *right_l = degen_tree(root->right);

    node_t *head = merge_lists(left_l, root, right_l);
    return(head);
}

DFS for tree, if node doesn't have children remove node from parent and node become root of tree.

class TreeNode
{
    int data;
    TreeNode left=null,right=null;
    TreeNode(int data)
    {
        this.data=data;
    }
    TreeNode rightMost()
    {
        TreeNode tra=this;
        while(tra.right!=null)
            tra=tra.right;
        return tra;
    }
}
class BTtoDTSorted
{
    static TreeNode head=null,tail=null;
    static void addToList(TreeNode node)
    {
        if(head==null)
        {
            head=node;
            tail=head;
            return;
        }
        if(head.data>node.data)
        {
            node.right=head;
            head=node;
        }
        else if(tail.data<node.data)
        {
            tail.right=node;
            tail=node;
        }
        else 
        {
            TreeNode tra=head;
            while(tra.right!=null)
            {
                if(tra.right.data>node.data)
                {
                    TreeNode temp=tra.right;
                    tra.right=node;
                    node.right=temp;
                }
            }
        }
    }
    static void DFS(TreeNode head)
    {
        if(head.left!=null)
            DFS(head.left);
        System.out.print(head.data+", ");
        if(head.right!=null)
            DFS(head.right);
    }
    static void TreetoList(TreeNode head)
    {
        TreeNode left,right=head.right;
        if(head.left!=null)
            TreetoList(head.left);
        System.out.println("head,data "+head.data);
        addToList(head);
        head.left=null;
        if(right!=null)
            TreetoList(right);

}}

public void DegenerateTree(TreeNode root)
{
	if (root == null)
		return;
	
	var p = root;
	var stack = new Stack<TreeNode>();
	
	while (p != null)
	{
		if (p.Left == null && p.Right == null)
		{
			if (stack.Count > 0)
			{
				var node = stack.Pop();
				p.Right = node;
			}
		}
		else if (p.Left != null)
		{
			if (p.Right != null)
				stack.Push(p.Right);
			p.Right = p.Left;
			p.Left = null;
		}
		p = p.Right;
	}
}

some c# code. Suppose it works ok.

static Tuple<Node, Node> Transform(Node node)
        {
            Node begin, end;

            if (node.Left != null)
            {
                var result = Transform(node.Left);
                begin = result.Item1;
                result.Item2.Right = node;
                node.Left = null;
            }
            else
            {
                begin = node;
            }

            if (node.Right != null)
            {
                var result = Transform(node.Right);
                end = result.Item2;
                node.Right = result.Item1;
            }
            else
            {
                end = node;
            }
            return new Tuple<Node, Node>(begin,end);
        }

static class Node {
		int value;
		Node left;
		Node right;
		
		public Node() {}
		public Node(int value, Node left, Node right) {
			this.value = value;
			this.left = left;
			this.right = right;
		}
	}
	
	static class Result {
		Node head;
		Node tail;
	}

	static Result transform(Node root) {
		if (root == null) return null;
		Result result = new Result();
		result.head = root;
		result.tail = root;
		if (root.left != null) {
			Result t = transform(root.left);
			result.head = t.head;
			t.tail.right = root;
			root.left = null;
		}
		if (root.right != null) {
			Result t = transform(root.right);
			root.right = t.head;
			result.tail = t.tail;
		}
		return result;
	}

/* BST to link List */

struct node_t{
    int data;
    struct node_t *left;
    struct node_t *right;
}

node_t *mergeLists(node_t *left, node_t *node, node_t *right)
{
    assert(node != NULL);
    node_t *head;
    
    /* merge left and node */
    if(left!=NULL){
        head = left;
        while(left->next != NULL){
            left = left->right;
            left->right = NULL;
        }
        left->next=node;
    }else{
        head = node;
    }
    
    /* merge node and right */
    node->next=right;
    return head;
}

node_t *convertToList(node_t *node)
{
    if(NULL == node)
        return NULL;
        
    node_t *left = convertToList(node->left);
    node_t *right = convertToList(node->right);
    
    return mergeLists(left, node, right);
}

/* BST to Double Link List */

struct node_t{
    int data;
    struct node_t *left;
    struct node_t *right;
}

node_t *mergeDLists(node_t *left, node_t *node, node_t *right)
{
    assert(node != NULL);
    node_t *head;
    
    /* merge left and node */
    if(left!=NULL){
        head = left;
        while(left->right != NULL){
            left = left->right;
        }
        left->right = node;
        node->left = left;
    }else{
        head = node;
    }
    
    /* merge node and right */
    node->right=right;
    right->left = node;
    return head;
}

node_t *convertToDList(node_t *node)
{
    if(NULL == node)
        return NULL;
        
    node_t *left = convertToList(node->left);
    node_t *right = convertToList(node->right);
    
    return mergeLists(left, node, right);
}