Google on-site 1

gistfile1.java

Node lastVisted = null;

void convertTree(Node root) {
	if (root == null) {
		return;
	}
	convertTree(root.left);
	if (lastVisited != null && lastVisited.right == null) {
		lastVisited.right = root;
		lastVisited.t |= RIGHT_CONVERTED;
	}
	if (root.left == null) {
		root.left = lastVisited;
		root.t |= LEFT_CONVERTED;
	}
	lastVisited = root;
	convertTree(root.right);
}

class Node {
  Node next, random;
  char data;
}

Node duplicateLinkedList(Node head) {
	Node current = head;
	Node newHead = null;
	Node newCurrent;
	while (current != null) {
		Node newNode = new Node(current.data);
		if (newHead == null) {
			newHead = newNode;
		}
		if (newCurrent != null) {
			newCurrent.next = newNode;
		}
		newCurrent = newNode;
		newCurrent.r = current;
		Node oldCurrent = current;
		current = current.next;
		oldCurrent.next = newCurrent;
	}

	newCurrent = newHead;
	while (newCurrent != null) {
		newCurrent.r = newCurrent.r.r.next;
		newCurrent = newCurrent.next;
	} 
	return newHead;
}