CareerCup

reverse preorder..
right left root

prev=NULL


everytime acces the node set its right to prev
and prev=current

in the end we will have a sort of linked list whose 1 st element is root then left child then right,.,,

code is simple..

any thoughts???

private static Node transform(Node root) {
		Node right = root.right;
		Node rightMost = root;

		if (root.left != null) {
			rightMost = transform(root.left);
			root.right = root.left;
			root.left = null;
		}

		if (right == null) {
			return rightMost;
		}

		rightMost.right = right;
		rightMost = transform(right);
		return rightMost;
	}

here my iterative solution in C++:

void transform_to_preorder_traversal() {
		stack<Node*> s;
		queue<Node*> path;
		
		s.push(get_root());
		
		while(!s.empty()) {
			Node *n = s.top();
			s.pop();
			
			path.push(n);
			
			if(n->right) {
				s.push(n->right);
			}
			
			if(n->left) {
				s.push(n->left);
			}
		}
		
		bool init = true;
		Node *prev = NULL;
		
		while(!path.empty()) {
			if(init) {
				init = false;
				prev = path.front();
				path.pop();
			}
			
			Node *current = path.front();
			prev->right = current;
			path.pop();
			
			prev = current;
		}
	}

simplified version in C++:

void transform_preorder_traversal() {
		stack<Node*> s;
		Node *prev = NULL;
		bool init = true;
		
		s.push(get_root());
		
		while(!s.empty()) {
			Node *n = s.top();
			s.pop();
			
			if(!init) {
				prev->right = n;
			}
			prev = n;
			
			path.push(n);
			
			if(n->right) {
				s.push(n->right);
			}
			
			if(n->left) {
				s.push(n->left);
			}
			
			if(init) {
				init = false;
			}
		}

Here's another recursive implementation in Java:

public Node<T> transformToRight(Node<T> node) {
		if (node == null) {
			return null;
		}
		
		if(node.left == null) {
			return node;
		}
		
		Node<T> leftSubtree = transformToRight(node.left);
		Node<T> rightSubtree = transformToRight(node.right);

// Move left subtree to the right of the current root		
		node.right = leftSubtree;

// Traverse the leftsubtree till the last node. And set right child as the right child of current root
		while (leftSubtree.right != null)
			leftSubtree = leftSubtree.right;
		leftSubtree.right = rightSubtree;

		return node;
	}

The idea is like this:

1. For each node, we call transform on it's left and right node. As we do have to transform both the subtrees.
2. Once we have the left subtree and right subtree transformed, we add the left subtree in between the parent and the right subtree. Note, we have to set the parent.next = leftsubtreeroot, and traverse the left subtree till we reach the leaf, and set the next of that leaf to the parent.right

Hi, i had a small bug in my code, all left pointers should be set to NULL...to make sure the tree is deleted correctly when calling the destructor of the tree...

void translate_preorder_traversal() {
		stack<Node*> s;
		Node *prev = NULL;
		bool init = true;
		
		s.push(get_root());
		
		while(!s.empty()) {
			Node *n = s.top();
			s.pop();
			
			if(!init) {
                prev->left = NULL;
				prev->right = n;
			}
			prev = n;
					
			if(n->right) {
				s.push(n->right);
			}
			
			if(n->left) {
				s.push(n->left);
			}
			
			if(init) {
				init = false;
			}
		}

void PreorderTraverse(queue<Node*>& myQueue, Node* head)
{
if (NULL == head)
{
return;
}

myQueue.push(head);
PreorderTraverse(myQueue, head->left);
PreorderTraverse(myQueue, head->right);
}

void Transform(Node*& head)
{
if (NULL == head)
{
return;
}
std::queue<Node*> myQueue;
PreorderTraverse(myQueue, head);

Node* pre = myQueue.front();
myQueue.pop();

head = pre;

while (!myQueue.empty())
{
Node* cur = myQueue.front();
myQueue.pop();
pre->right = cur;
pre->left = NULL;
pre = cur;
}
pre->right = NULL;
}

node *modifyPreorder(node *root) {
  node *temp = root, *ret = root;
  if(root->left) {
    temp = modifyPreorder(root->left);
  }
  if(root->right) {
    ret = modifyPreorder(root->right);
    temp->right = root->right;
  } else {
    ret = temp;
  }
  if(root->left) {
    root->right = root->left;
  }
  return ret;
}

Recursive call to transform everything to a “Right” node.

public static void Transform(Node r)
        {
            if (r == null)
                return;
            if (r.Left != null)
                Transform(r.Left);
            if (r.Right != null)
                Transform(r.Right);
            if (r.Right != null  )
            {
                if (r.Left != null)
                {
                    RightMost(r).Right = r.Left;
                    r.Left = null;
                }
            }
            else
            {
                if (r.Left != null)
                {
                    r.Right = r.Left;
                    r.Left = null;
                }
            }
        }
        public static Node RightMost(Node n)
        {
            if (n==null)
                return null;
            while(n.Right != null)
            {
                n = n.Right;
            }
            return n;
        }

public:
	void flatten(Node *root) {
		flatten(root, nullptr);
	};
private:
	void flatten(Node *root, Node *tail) {
		if (root == nullptr)
			return tail;
		root->right = flatten(root->left, flatten(root->right, tail));
		root->left = nullptr;
		return root;
	}

void modify_subtree (tree *root, tree **new_ptr_addr)
{
        tree *right = root->r_child;
        root->r_child = root->l_child;
        *new_ptr_addr = right;
}

tree **convert_to_preorder(tree *root)
{
        if (root)
        {
                tree **left = convert_to_preorder(root->l_child);
                tree **right = convert_to_preorder(root->r_child);

                if (!left && !right)
                {
                        return &(root->r_child);
                }

                if (left)
                {
                        modify_subtree (root, left);
                }

                if (right)
                {
                        return right;
                }

                else
                {
                        return &(root->r_child);
                }
        }
        return NULL;
}

idea is like:
for leaf node, address of right child is returned
for non-leaf node, if left subtree exist then it has returned a address that address should not point to right of this node & node's right should point to node's left.
if for non-leaf node, left subtree doesnot exist, do nothing/
for non-leaf node, if right subtree exist then this right subtree must have returned a address that address should be returned 
for non-leaf node, if right subtree does not exist, then address of right child should be returned

can anyone verify this for me

struct node
{
	struct node* left;
	struct node* right;
	int num;
};

typedef struct node* tr;
tr pre(tr head)
{
	tr cur = NULL,lf = NULL,ri = NULL,temp=NULL;
	if(head==NULL)
		return NULL;
	lf = pre(head->left);
	rf = pre(head->right);
	
	if(head->left!=NULL)
	{
		if(head->right==NULL)
		{
			head->right = head->left;
			head->left = NULL;
			return head;
		}
		else
		{
			temp = head->left;			
			while(temp->right!=NULL)
				temp = temp->right;
			temp->right = head->right;
			head->right=head->left;
			head->left=NULL;
			return rf;
		}
	}
	if(head->right==NULL)
	{
		return head;
	}
	return head;
}

My function logic below might seem a little complicated at first but upon going through some test cases, you should be able to get it.
eg-

initial tree:

1
          /  \
        2    6
       /        \
     3          7
    /  \
  4    5

final tree:

1
   \
     2
       \
         3
           \
             4
               \
                5
                  \
                    6
                      \
                       7

static *var , c=1;    //these two static variables are used to keep track of the actual root node
void modtree(root)
{
   if (root==null)
    return;
   if (c==1)    //upon first call, we get the root node and store it's location for later use
   { 
     var=root;
     c=0;
    }
 modtree (root->left);   // an inorder traversal begins
if (root!=var)    //if this current node is not the root node of the original tree
{
   if (root->left!=null)    // cases: where current node has only a left child or both left or right ch.
    {
       if(root->right=null)     //only a left child: bring the child to right of the current node
     {   root->right=root->left;
         root->left=null; 
        }
 else                                //both children of current node present
       { 
	  root->left->right=root->right;   //make the right child , the right child of the left child of                
                                                             //current node
 	  root->right=root->left;         //make the left child the right child of the current node
      root->left=null;
	}
      }
     }
      else                        //case when the current node is the root node; when this step is 	  
                                    // reached, the left and right sub-trees of the root node will be right- 
                                    // aligned
      {
	 tmp=root->left;
	 while(tmp->right!=null) // reach the last child of the left sub-tree
	 tmp=tmp->right;
       tmp->right=root->right;   //attach the right subtree of the root node to the right of the last 
                                                 //child of left sub-tree
       root->right=root->left;    //make the left sub-tree the right child of the root node; we will  
                                               //have a degenerate right-aligned linked list. this is the final step.   
root->left = null;
    }
    modtree(root->right);
}

in inorder traversal ...
if the node has left child .......store the right child
make the right pointer point to the left child ....
traverse the whole right sub tree just formed to point the stored right child as right child





void modify(struct node *t){
if(t!=NULL){

modify(t->left);
struct node *temp;
if(t->left){
temp=t->right;
t->right=t->left;
while(t->right)
t=t->right;
t->right=temp;

}
modify(t->right);

}

}


any thoughts ..??

A simple and efficient iterative approach :

Do the usual iterative stack based preorder traversal of your tree.....
every time you pop a node from the stack , make the stack top item(if present ) its right child
otherwise set its right child to NULL...

public TreeNode modifyPointer(TreeNode root) {

if (root == null) {

return root;
}

else {

if (root.right == null) {
root.right = modifyPointer(root.left);
root.left = null;
return root;
}

else {
TreeNode temp = root.right;
root.right = modifyPointer(root.left);
TreeNode iter = root.right;
while (iter.right!=null) {
iter = iter.right;

}

iter.right = modifyPointer(temp);
root.left = null;
return root;
}
}
}

class tree* newRoot = NULL;
class tree* prev = NULL;
void modifyTree(class tree* root)
{
    if(root)
    {
        modifyTree(root->left);
     
        if(!newRoot)
        {
            newRoot = root;
            prev = root;
        }   
        if(root && prev && root != prev)
        {
            prev->right = root;
            root->left = NULL;
            prev = root;
        }
        modifyTree(root->right);
    }
}