## Google Interview Question

**Country:**United States

@Scott, @pavelkushtia, please, read comments throughout this page, including the comments of the problem reporter. Recursion in this case makes it greater than O(1) memory, at least O(logn) to keep stack. O(1) is clearly problem requirement, as was clarified numerous times in this page, including the clarification of the problem reporter. Such solution does exist, see my solution, @zortlord and myself tested it really thoroughly for correctness and time/space complexity,

Here is the code that loosely follows my previous explanation (below the code).

Relinking a node with its next on the left (grand)*child that has no right child.

Do this for every (often unlinked) left child.

Back up right very same links that were relinked until left does not point back.

If reached end (no right node), work completed.

Otherwise, relink right (similarly as left in first step) just once and repeat from the begining for (often unlinked) right child.

```
//return tail of double-linked list
static Node convert(Node root) {
while (true) {
while (root.left != null && root != root.left.right) {
root = relinkLeft(root);
}
//go back
while (root.right != null && root == root.right.left) {
root = root.right;
}
if (root.right == null) return root;
root = relinkRight(root);
}
}
static Node nextOnLeft(Node n) {
Node left = n.left;
while (left.right != null && left != left.right.left) left = left.right;
return left;
}
//return orphan
static Node relinkLeft(Node n) {
Node orphan = n.left;
Node left = nextOnLeft(n);
n.left = left;
left.right = n;
return orphan;
}
static Node nextOnRight(Node n) {
Node right = n.right;
while (right.left != null && right != right.left.right) right = right.left;
return right;
}
//return orphan
static Node relinkRight(Node n) {
Node orphan = n.right;
Node right = nextOnRight(n);
n.right = right;
right.left = n;
return orphan;
}
```

EDIT2

Node properties:

noLeftChild is a Node that has no left child

nextOnLeft is a next Node on the left to noLeftChild

noRightChild is a Node that has no right child

nextOnRIght is a next Node on the right to noRightChild

Single node can have multiple of above roles

right of nextOnLeft points to noLeftChild

left of noLeftChild points to nextOnLeft

right of noRightChild points to nextOnRight

left of nextOnRight points to noRightChild

Traversal, that I will detail later, that takes O(1) space, including no stack from recursion, by leveraging build so far re-linking.

For two consecutive elements that have matching properties do re-linking.

Code will follow in some time.

'Build up a list' sounds like O(N) memory if the tree was degenerated. I got your idea however an elegant implementation is not that straightforward.

Yes, I misunderstood the assignment atatement, I thought new List has to be created and after that no extra space

I don't think the code as it is O(n). If I have a balanced tree like

```
____1
___/___\
__2____3
_/__\__/__\
4__5_6__7
```

Then the entire left side gets built correctly, but when relinkRight gets called and returns node 5, the while(true) reexecutes and then traverses completely back over the left side again before working on the right side of node 1. I think this approach may be O(n^2) due to the retraversals to the left.

@zortlord, than you for feedback. I did not understand it though because you said node 5 returns after left side is complete, but 5 is on left side, can you clarify.

Consider this:

How many time you re-walk the links?

Every incomplete sub-tree will have shortcut back.

Think about the walk trace in DFS of tree, it also traces back waht had been walked but still walk is O(n)

@zortlord Also note that:

while (root.left != null) {

root = relinkLeft(root);

}

Happens after step into right, relinkRight steps into new orphan on right

Starting at convert using the example tree, the tree,

in left link while,

1.left <-> 5.right and 2 becomes root

2.left <-> 4.right and 4 becomes root

no more lefts so moving on

in 'go back' while

2 becomes root

5.left == null so moving on

relink right makes

2.right <-> 5.left and 5 becomes root.

repeating main while loop

in left link while: (this is the part that I think is repeating inappropriately)

5.left <-> 2.right and 2 becomes root.

2.left <-> 4.right and 4 becomes root.

4 has no left node, so loop breaks

in next while loop, 1 become root after 3 iterations

...

@zortlord, thank you, let me investigate, the intention was to go back from 5 to 1. if it does not do that it is an error that I think easy to fix.

@zortlord, I fixed it, many thanks for valuable feedback. I debugged it better this time and now certain time complexity is as DFS walk.

I think this algorithm fails for this input:

```
.......1
..../.....\
..2.........3
....\
......4
..../
..5
```

@zortlord I walk through this code in my head on the tree above, it should work, pretty certain. I am going to verify it in Eclipse very soon.

@zortlord, I just run it to verify on your last tree, it works perfect. False accusation :)

I think I deserve up-vote, don't I? BTW, I up-voted you for your rigorous verification work.

Misread one little '!' while computing by hand. Funny how that can change a complete analysis. HOWEVER, this is not a O(n) algorithm... I think it's closer to O(n log n). This can be seen when you test it with a fully populated tree. The following is test code (slightly modified to track the number of computation iterations):

```
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
public class TreeToDll {
static int iterations = 0;
public static void main(String[] args){
Node root = constructTree(3);
//run the test
Node list = TreeToDll.convert(root);
//move to head
while(list.left != null){
list = list.left;
}
//output list
while(list != null){
System.out.print("" + list.val + " -> ");
list = list.right;
}
System.out.println("\niterations = "+iterations);
}
private static Node constructTree(int size) {
Node root = new Node();
root.val = 1;
LinkedList<Node> list = new LinkedList<Node>();
LinkedList<Node> alt = new LinkedList<Node>();
LinkedList<Node> temp = null;
int depth = 1;
int val = 1;
list.add(root);
while(depth < size){
while(!list.isEmpty()){
Node node = list.removeFirst();
Node left = new Node();
val++;
left.val = val;
node.left = left;
alt.add(left);
Node right = new Node();
val++;
right.val = val;
node.right = right;
alt.add(right);
}
temp = list;
list = alt;
alt = temp;
depth ++;
}
return root;
}
static class Node{
Node left, right;
int val;
}
//return tail of double-linked list
static Node convert(Node root) {
while (true) {
while (root.left != null && root != root.left.right) {
iterations ++;
root = relinkLeft(root);
}
//go back
while (root.right != null && root == root.right.left) {
iterations ++;
root = root.right;
}
if (root.right == null) return root;
iterations ++;
root = relinkRight(root);
}
}
static Node nextOnLeft(Node n) {
Node left = n.left;
while (left.right != null && left != left.right.left){
iterations ++;
left = left.right;
}
return left;
}
//return orphan
static Node relinkLeft(Node n) {
Node orphan = n.left;
Node left = nextOnLeft(n);
n.left = left;
left.right = n;
return orphan;
}
static Node nextOnRight(Node n) {
Node right = n.right;
while (right.left != null && right != right.left.right) {
iterations++;
right = right.left;
}
return right;
}
//return orphan
static Node relinkRight(Node n) {
Node orphan = n.right;
Node right = nextOnRight(n);
n.right = right;
right.left = n;
return orphan;
}
}
```

@zortlord, Your excellent verification program actually assured me this is O(n). At depth 10 number of nodes to iteration ratio converges to 0.40: 2^10 - 1 nodes divided by 2537 iteration.

At depth 15 it still stays 0.40: 2^15 - 1 nodes divided by 81887.

Because nodes to iteraton ratio converges and does not change after convergance, we can surely say that number of nodes is assymptotically proportinal to number of iterations, which implies O(n).

This is really good way to verify algorithms, I am surelly up-voting your verification driver.

@CT

I didn't go any higher than 10 deep on the tree and their appeared to be an increasing multiplier on the amount of iterations. At about 2^20 nodes (20 deep) it appears that the multiplier bottoms out at about 2.5 * n iterations are needed to solve each tree. So it would be O(2.5 n) -> O(n).

This is pretty normal, even in DFS walk you will have to go back many times and will have more edge-walking iterations than nodes. You can actually simulate DFS tree walk if your node has also link to parent.

You can use anything unless you do not copy the tree or additional complexity is not constant. I am thinking of recursive algorithm that transfer each BST subtree into a linked list and then merges. Here is the sketch:

```
public Node convertBST(node root) {
root = bst2linkedList(root);
return connectLinkedList(root);
}
// Use only 'left' to form a singly linked list.
private Node bst2linkedList (Node curr) {
// Leaf node
if (cur.left == null && cure.right == null)
return curr;
// Left subtree
Node aux;
if (curr.left != null) {
aux = bst2linkedList(curr.left);
curr.left = aux;
}
// Right subtree
if (curr.right != null) {
aux = bst2linkedList(curr.right);
Node last = curr.right;
// This can be further optimized such that
// 'right' points directly to the last node:
while (last.left != null)
last = last.left;
curr.right = last;
last.left = curr;
curr = curr.right;
}
return curr;
}
// Connect 'right' to form a doubly linked list
private Node connectLinkedList(Node root) {
Node curr = root;
while (curr.left != null) {
Node next = cur.left;
next.right = curr;
}
return root;
}
```

```
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static class Node
{
Node left,right;
String value;
boolean isVisited;
public Node(String in)
{
this.value = in;
this.left = null;
this.right = null;
}
}
static class Tree
{
Node rt;
public Tree(Node r)
{
this.rt = r;
}
public void convertBstToDLinkedList(Node root)
{
if(root == null) return;
if(root.isVisited == false)
{
convertBstToDLinkedList(root.left);
root.isVisited = true;
if(root!= null && root.right == null && root.left !=null)
{
root.left.right = root;
}
else if(root!= null && root.right != null && root.left != null)
{
root.left.right = root;
root.right.left = root;
}
else if(root != null && root.left == null && root.right !=null)
{
root.right.left = root;
}
convertBstToDLinkedList(root.right);
}
}
public void printHeadNode()
{
while(rt.left != null)
{
rt = rt.left;
}
System.out.print(" "+rt.value);
while(rt != null)
{
System.out.print(" "+rt.value);
rt = rt.right;
}
}
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Node G = new Node("G");
Node A = new Node("A");
Node T = new Node("T");
G.left = A;
G.right = T;
Tree root = new Tree(G);
root.convertBstToDLinkedList(G);
root.printHeadNode();
}
}
```

You can not change the given implementation of Node. If you create an extension of Node it looks like you end up with O(N) memory;

C# solution for creating a doubly linked list using existing memory, notice the recursion will take up memory too

```
public static Node ConvertBstToListReturnHead(Node root)
{
return ConvertBstToList(root).Item1;
}
public static Tuple<Node, Node> ConvertBstToList(Node root)
{
if (root == null)
{
return null;
}
var left = ConvertBstToList(root.Left);
var right = ConvertBstToList(root.Right);
Node first=root;
Node last=root;
if (left != null)
{
root.Left = left.Item2;
left.Item2.Right = root;
first = left.Item1;
}
if (right != null)
{
root.Right = right.Item1;
right.Item1.Left = root;
last = right.Item2;
}
return new Tuple<Node, Node>(first, last);
}
```

In-order traversal of the tree will be equivalent to the doubly linked list behavior. You can do in-order traversal two ways: Left-Root-Right or Right-Root-Left for the ascending and descending ordered manifestation of the sort.

Exactly...I have not idea what all these other answers are about! This one makes that most sense.

Basically you can do an inorder traversal, but keep track of a global 'previous' node. on each node we visit in the traversal, set the previous node's next pointer to the current node we are on. the current node's previous pointer to the previous global node. then set the current node as the global node and continue the traversal

```
Node global;
public void linkedList(Node n) {
if (n == null) { return; }
linkedList(n.left);
if (global == null) {
global = n;
return;
}
global.next = n;
n.previous = global;
global = n;
linkedList(n.right);
}
```

```
void convertBSTToList(node *root, node *&prev, node *&head)
{
if (!root) return;
convertBSTToList(root->left, prev, head);
if (prev)
prev->right = root;
else
head = root;
root->left = prev;
prev = root;
convertBSTToList(root->right, prev, head);
return;
}
```

We start by building the double linklist by always getting the minimum of the tree and delete the minimum node in the tree.

```
Node* GetMinNode(Node** node)
{
if (node == null)
return null;
Node* tmp = node;
if (node->left == null){
node = node->right;
return tmp;
}
while(node->left != null){
tmp = node;
node = node->left;
}
tmp->left = null;
return tmp;
}
Node* BST_to_DLL(Node* tree)
{
Node * head;
head = GetMinNode(&tree);
if (head == null)
return null;
Node * tmp = head;
Node * tmp2;
head->left = null;
tmp2 = GetMinNode(&tree);
while(tmp2 != null){
tmp->right = tmp2;
tmp2->left = tmp;
tmp = tmp2;
tmp2 = GetMinNode(&tree);
}
tmp->right = null;
return head;
}
```

Look like most of you do inorder tree traversal. I guess I do the same

```
bool BST2List(Node* node, Node** front, Node ** back, Node ** head)
{
if (node == null)
return False;
if (BST2List(node->left, &front, &back, &head)){
back->right = node;
node->left = back;
}
else{
if (head == null)
head = node;
front = node;
node->left = null;
}
if(BST2List(node->right, &front, &back, &head)){
front->left = node;
node->right = front;
}
else{
back = node;
node->right = null;
}
return True;
}
```

Why is using recursion cause memory usage to be O(n)? Every time I call recursively, I did not increase additional memory usage except increase the stack pointer. Is that the interview question require both instruction memory and data memory together added up to be O(1)? The question said do it in place. Which is what I did. I did not even use temporary variables to hold any temporary data or pointer. Just the stack pointer. The question never said no recursion. When people said memory complexity, I thought they usually refer to data memory (the variable or array that we created), not the instruction memory (number of functions, recursion). I am wrong on this?

Recursion always implies stack, always. The fact that you did not explicitly created it does not mean it does not exist.

To be fair, if you have two recursive calls left and right, that is normally O( log(n) ) memory, not O(n). But still violates O(1)

Then my previous solution is better, getting the minimum from the tree and then build the double linklist. But the runtime will be n^2.

By the way CT, you are assuming that the BST is balance. If it is balance, then it will be O(log n). However, the worst case can still be O(n) since the BST can be just only left child for all node or right child for all node or one child at each node.

For Google, it is normally just first step to make sure problem requirements are fulfilled, normally if you don't get optimal, you get no vote. However, this problem is ridiculously difficult, it took me hours to get both right. I am thinking this is the goal to learn how to solve problems like this optimally in 45 minutes.

@CT / @hiuchan

The reason that it's O(n) is that the BST is not necessarily balanced. It could have only left branches. In that case, the function would be recursively called n times.

How about using big Omega for that. In big O we can consider an average case, I believe.

Big O is is generally considered the smallest possible *upper* bound. In this case it would be O(n).

Big Omega is generally the smallest possible *lower* bound which would be Omega(log n).

@zortlord I really implied to say big Theta, not big Omega, my mistake - thanks for correction

By the way, I thought about that. using recursion in this question for interview is good. Remember during the interview, the objective is Google want to see your problem solving skill. Using recursive mean you know how to solve problem using divide and conquer. Plus memory complexity of O(1) in this case simply mean the Node is this tree should simply reuse to become each node in the double linklist. yes, maybe you should avoid recursion when you work inside Google and try to convert a BST with 100 millions tree node into double linklist. but not during the interview session.

I think this problem clearly wants you too reuse partial result to enable DFS or BFS or whatever reasonable walk.

Why we always use recursion (with implied stack) or queue for BFS? Because we don't have link back to parent.

Now if no-one can solve this problem in 45 minutes, Google will compare who had done more, who come closer and all the thing you mentioned will be considered. But it will all be considered as partial, top result. As far as if they will let you use recursion in the framework of partial answer, it is up to them - but O(1) memory may be the most important statement of the problem and they may not. They don't care if "you know how to solve problem using divide and conquer", they already know it from screening. They wan to see you with the problem and O(1) mem may very well be the problem.

I will have to disagree with you. if we use recursion because of we don't have link back to parent. We can always save the previous link, which is a constant space (O(1).) The goal is to understand trade off. Such as trade off memory space to improve runtime performance. If what you say is true. Then people at Google will never program with dynamic programming. They will never use quick sort or merge sort (both quick sort and merge sort are divide and conquer problem)

You cannt save one back link, you have to stack them up for DFS, that is why there is a stack.

All the tradeoff things are nice, dynamic programing are nice for wide range of many different problems they will ask you. But this particular problem may all be about O(1) memory. Google's problem are beyond just divide and conquer skills, their do make sure you have them - but more.

That will depend on how you think about O(1) memory. I do not consider stack pointer increment consider as part of memory complexity. when the question asked doing it in place. This is what I consider as O(1). When people compare quick sort vs merge sort, people all know that they both run as O(n log n). The only reason why quick sort is better than merge sort is because you can easily do quick sort in place whereas, merge sort in place implementation is a lot harder.But quick sort has memory complexity of O(log n) simply because everytime you recursively call quicksort, there are new variables in every stack frame ('hi' and 'low'). But in my case, I did not declare any new variables. I only pass variables by references. The only only think that I can think of where you can argue about is the pointers to the variables that I pass in. Well, if that is something that Google tried to avoid, I guess Google is not the company for me. I was in Google onsite interview few months back and during the phone screen, I answered exactly with recursion. Maybe different interviewer has different requirement. Who know.

1. Recursion is always stock. If you are dealing with huge amount of data you sometimes must avoid it because most languages have limit to such stack. Try implementing some recursive method - let's say Fibonachi recursively ( F(i)=F(i-1)+F(i-2) even though DP method much more efficient, but for the education purpose) and run for large ith Fibonachi number. You will be surprised how quickly you will reach the limit.

2. Recursion is not bad in many many problems. They ARE NOT taboo in Google interview unless the SPECIFIC problem places taboo.

3. In-place and O(1) memory are two different things. May be this problem asked about in-place but not about O(1), may be a person who posted can verify. If your stack runs out of stack memory, the fact it is in place algorithm will not help you.

4. The problems Google ask is not always about what they do, but for testing problem solving.

5. And one more note about recursion. If a method is not dependent on recursive call return to complete, it may not need to stack it up. This is why perhaps sorting method do not consider its memory cost. Once you are given your divide, you can finish it independently and compiler may realize it and not need to stack it for later un-stacking. However, this is normally not the case in tree walking because you have to return from left to go to right so the method is dependent on un-stacking to complete it.

This can be EXTREMELY easy if you build up the list by recursive construction and returning the start and end of each sublist:

```
static class Node{
Node left, right;
String val;
}
public static Node flatten(Node root){
if(root == null){
return null;
}
return flattenRecur(root)[0];
}
private static Node[] flattenRecur(Node node){
Node start = node;
Node end = node;
Node[] results = null;
if(node.left != null){
results = flattenRecur(node.left);
start = results[0];
results[1].right = node;
node.left = results[1];
}
if(node.right != null){
results = flattenRecur(node.right);
end = results[1];
results[0].right = node;
node.right = results[0];
}
if(results == null){
return new Node[]{start, end};
}
results[0] = start;
results[1] = end;
return results;
}
```

Actually, forgot to consider the memory cost of recursion... the above approach will work but it incurs memory complexity due to recursion along with every other recursive approach.

Here is a non-recursive version that is O(1) in memory complexity and O(n^2) in algorithmic complexity for an unbalanced tree ( O( n Log n) for a balanced one):

```
static class Node{
Node left, right;
String val;
}
public static Node flatten(Node root){
if(root == null){
return null;
}
Node[] calc = popLeft(root);
root = calc[1];
Node head = calc[0];
Node tail = head;
while(root != null){
calc = popLeft(root);
tail.right = calc[0];
calc[0].left = tail;
tail = calc[0];
root = calc[1];
}
return head;
}
//removes the leftmost node and fixes the tree
//returns Node array where [0] is the removed node and
//[1] is the new root of the tree
private static Node[] popLeft(Node node){
if(node.left == null){
return new Node[]{node, node.right};
}
Node parent = node;
Node child = parent.left;
while(child.left != null){
parent = child;
child = child.left;
}
Node[] results = new Node[]{child, node};
parent.left = child.right;
return results;
}
```

Thus far, I think hiuhchan's and my solution are the only non recursive ones that can solve the following tree. If I'm wrong, please, someone show me a better way because I don't like the approach. It seems "wrong".

```
.....1
../.....\
.2.......3
...\
.....4
.../
.5
```

Edit: CT's solution does work and it appears to be O(n)

Here is a Java version with running time O(n), memory O(1) and non-recursive. The idea that makes the algorithm run without a stack (i.e. memory O(log(N))) is: if the current node have left child, go to the left but attach the current node to its right most sub-tree to come back.

Updated: Make doubly linkedlist

```
public static Node convertBST2LinkedList(Node root)
{
Node current=root;
int count=0;
Node front=null;
while(current!=null)
{
//if the current left is null
if(current.left==null){
// System.out.println(current.val); //print out the value
if(count==0) front=current;
count++;
//Convert here
current=current.right; //Go to right
}else{
Node temp=current.left;
while(temp.right!=null){
temp=temp.right;
}
temp.right=current;
temp=current;
current=current.left;
temp.left=null; //cut left child
}
//else
}
//Make doubly linkedlist
Node temp2=front;
if(temp2!=null){
while(temp2.right!=null){
temp2.right.left=temp2;
temp2=temp2.right;
}
}
return front;
}
```

This code doesn't work. The results are supposed to be a doubly linked list and this creates only a singly linked list using the right connections.

@zortlord, you seem to be verifying code rigorously. I made sure I fulfilled every requirement of the problem, maybe the only person in this wall. I also tested my solution rigorously to make sure it works. Just curious, is there any reason you are not up-voting my solution?

@zortlord: that's true. I have just added a loop to make doubly linkedlist at the end of method. Everything is good now.

O(n) solution

inorder traversal of tree:

```
void traversal( node treenode , node head ){
static node prev = null;
if( treenode == null )
return;
traversal( treenode.left , head );
if( prev == null )
head = treenode;
else{
treenode.left = prev;
prev.right = treenode;
}
prev = treenode;
traversal( treenode.right , head );
}
```

```
public Node connect (Node root){
if (root == null) return null;
Node left = connect (root.left);
if (left != null) {
left.next = root ;
root.pre = left ;
}
Node right = connect (root.right);;
if (right != null) {
root.next = right;
right.pre = root ;
}
return root;
```

}

What about this:

```
#include <string>
#include <iostream>
struct Node
{
Node (const std::string &v) : left(0), right(0), val(v){}
Node *left, *right;
std::string val;
};
void printTree (Node * root)
{
if (root)
{
printTree (root->left);
std::cout << root->val << " ";
printTree (root->right);
}
}
void printDLL (Node * dll)
{
while (dll)
{
std::cout << dll->val << " ";
dll = dll->right;
}
}
void moveNextToDLL (Node *&root, Node* &head, Node *&tail, bool asc)
{
Node *current (root);
if (asc)
{
Node *parent(0);
while (current->left)
{
parent = current;
current = parent->left;
}
if (parent)
{
if (current->right != 0) // have children
parent->left = current->right;
else
parent->left = 0;
}
else // no left nodes
root = root->right;
}
else
{
Node * parent(0);
while (current->right)
{
parent = current;
current = parent->right;
}
if (parent)
{
if (current->left != 0) // have children
parent->right = current->left;
else
parent->right = 0;
}
else
root = root->left;
}
if (tail)
{
tail->right = current;
tail = tail->right;
}
else
head = tail = current;
tail->right = 0;
}
Node * inplaceTransform (Node *root, bool asc = true)
{
Node *head, *tail(0);
while (root)
moveNextToDLL (root, head, tail, asc);
return head;
}
int main()
{
Node * root (new Node("D"));
root->left = new Node ("B");
root->left->left = new Node ("A");
root->left->right = new Node ("C");
root->right = new Node ("F");
root->right->left = new Node ("E");
root->right->right = new Node ("G");
printTree (root);
std::cout << std::endl;
root = inplaceTransform (root, true);
printDLL (root);
std::cout << std::endl;
return 0;
}
```

public class BST2DLL {

class Node {

Node left;

Node right;

double value;

Node (double value){

this.value = value;

}

}

Node bst2dll(Node root, boolean isLeft){

if (root == null){

return null;

}

Node nl = bst2dll(root.left, true);

Node nr = bst2dll(root.right, false);

// merge these 3 nodes

return merge(root, nl,nr,isLeft);

}

Node merge(Node root, Node nl, Node nr, boolean isLeft){

if (nl == null && nr== null){ return root;}

if (nl != null){

nl.right = root;

root.left = nl;

}

if (nr != null){

nr.left = root;

root.right = nr;

}

if (isLeft && nr == null){

return root;

}

if (!isLeft && nl == null){

return root;

}

if (isLeft){ // return the right most element

while(nr.right != null){

nr = nr.right;

}

return nr;

}else{ // return the left most element

while(nl.left != null){

nl = nl.left;

}

return nl;

}

}

public static void main(String[] args) {

BST2DLL bst2dll = new BST2DLL();

Node nd1 = bst2dll.new Node(1);

Node nd2 = bst2dll.new Node(2);

Node nd2point5 = bst2dll.new Node(2.5);

Node nd2point7 = bst2dll.new Node(2.7);

Node nd3 = bst2dll.new Node(3);

Node nd4 = bst2dll.new Node(4);

Node nd5 = bst2dll.new Node(5);

Node nd6 = bst2dll.new Node(6);

Node nd7 = bst2dll.new Node(7);

Node nd8 = bst2dll.new Node(8);

Node nd7and5 = bst2dll.new Node(7.5);

Node nd9 = bst2dll.new Node(9);

nd4.left = nd2;

nd4.right = nd6;

nd2.left = nd1;

nd2.right = nd3;

nd3.left = nd2point7;

nd2point7.left = nd2point5;

nd6.left = nd5;

nd6.right = nd7;

nd7.right = nd8;

nd8.left = nd7and5;

nd8.right = nd9;

Node bst2dll2 = bst2dll.bst2dll(nd4,true);

while(bst2dll2.left != null){

System.out.println(bst2dll2.value);

bst2dll2 = bst2dll2.left;

}

System.out.println(bst2dll2.value);

while(bst2dll2.right != null){

System.out.println(bst2dll2.value);

bst2dll2 = bst2dll2.right;

}

System.out.println(bst2dll2.value);

}

}

why not a super simple recursively build it from left most child:

```
ListNode head;
TreeToList(root){
head = null;
TreeToListR(root);
return head;
}
TreeToListR(node){
if (node.left != null) TreeToListR(node.left);
if (head == null) head = node;
else head.next = node;
TreeToListR(node.right);
}
```

Modified Morris traversal

```
BSTnode BSTtoDLL() {
BSTnode p = this;
BSTnode ppre=null;
while (p != null) {
if (p.left == null) {
p.left=ppre;
p = p.right;
}
else {
BSTnode temp = p.left;
BSTnode pre = null;
while (temp.right != null && temp.right != p) {
pre = temp;
temp = temp.right;
}
if (temp.right == null) {
temp.right = p;
temp.left = pre;
BSTnode pleft = p.left;
p.left=temp;
p=pleft;
} else {
ppre=p;
p = p.right;
}
}
}
p=this;
while (p.left != null)
p = p.left;
return p;
}
```

Here's my solution. O(n log n) time and O(1) space. Written in Javascript.

They won't let me post the JsFiddle link but it's at /576wxb88/7/ if you're interested in messing around with it.

```
var Node = function(left, right, val) {
return {
left: left,
right: right,
val: val
}
}
function linkBST(origRoot) {
var root = null;
var child = null;
var toLink = null;
var toLinkParent = null;
var dir, opp;
for (i = 0; i < 2; i++) {
if (i == 0) { dir = 'right', opp = 'left' }
else { dir = 'left', opp = 'right' }
root = origRoot;
while (true) {
child = root[dir];
if (!child) {
if (dir == 'left') { return root }
else { break; }
}
if (child[opp]) {
toLink = child;
toLinkParent = root;
while (toLink[opp]) {
toLinkParent = toLink;
toLink = toLink[opp];
}
if (toLink[dir]) {
toLinkParent[opp] = toLink[dir];
} else {
toLinkParent[opp] = null;
}
root[dir] = toLink;
toLink[opp] = root;
toLink[dir] = child;
root = toLink;
} else if (child[dir]) {
child[opp] = root;
root = child;
} else {
child[opp] = root;
if (dir == 'left') { return child }
else { break; }
}
}
}
}
```

Essentially, we start at the root and first traverse the right side (so that we can just return the last value on the left side as per specs). At each step, we find the minimum value in the right subtree (O(log n)) and place it between the current Node (root) and it's next child (or just link the child back to the current node if it is the min value). If the min value has a right subtree, we replace the min value with that subtree.

Once that's done, just repeat on the left side and you're done.

Algo: Implementation in C++

concept: re-use left/right concept in BST as prev/next concept in DLL

If the root of current tree has right child, recursively convert the right sub-tree into a DLL(Doubly Linked List) and add it after the root;

If the root of current tree has left child, recursively convert the left sub-tree into a DLL and add it before the root, return the first node of the left sub-tree; otherwise, return the root

Node* convertBST2DLL (Node* node) {

Node* first;

Node* last;

if (root==NULL) return NULL;

if (root->right!=NULL)

{

first = convertBST2DLL(root->right);

first->left=root;

root->right=first;

}

if (root->left==NULL)

return root;

else

{

first = convertBST2DLL(root->left);

last = findLast(first);

last->right=root;

root->left=last;

return first;

}

}

Node* findLast(Node* node){

while (node->right!=NULL) node=node->right;

return node;

}

Algo: Implementation in C++

concept: re-use left/right concept in BST as prev/next concept in DLL

If the root of current tree has right child, recursively convert the right sub-tree into a DLL(Doubly Linked List) and add it after the root;

If the root of current tree has left child, recursively convert the left sub-tree into a DLL and add it before the root, return the first node of the left sub-tree; otherwise, return the root

Node* convertBST2DLL (Node* node) {

Node* first;

Node* last;

if (root==NULL) return NULL;

if (root->right!=NULL)

{

first = convertBST2DLL(root->right);

first->left=root;

root->right=first;

}

if (root->left==NULL)

return root;

else

{

first = convertBST2DLL(root->left);

last = findLast(first);

last->right=root;

root->left=last;

return first;

}

}

Node* findLast(Node* node){

while (node->right!=NULL) node=node->right;

return node;

}

This is correct O(1) answer, flatten the tree in single linked list, then reverse back and put the left links in their place.

```
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* root_c=root;
TreeNode* r_left;
while(root!=NULL){
r_left=root->left; //rightmost left
if(r_left!=NULL) {
// find the rightmost node in the left child
while(r_left->right!=NULL) r_left=r_left->right;
r_left->right=root->right;
root->right=root->left;
root->left=NULL;
}
root=root->right;
}
// now make the left links
root=root_c;
TreeNode* pre;
while(root->right != NULL) {
pre=root;
root=root->right;
root->left=pre;
}
}
};
```

perform post order traversal and in each step insert the root between the rightmost left node and leftmost right node

```
def convertBSTInPlace(root):
if root is None:
return
convertBSTInPlace(root.left)
convertBSTInPlace(root.right)
last = root.left
while last and last.right:
last = last.right
head = root.right
while head and head.left:
head = head.left
if last:
last.right = root
root.left = last
if head:
root.right = head
head.left = root
```

Solution in C#

```
public static void Main()
{
var k = new TreeNode { left = null, right = null, val = 1 };
var p = new TreeNode { left = null, right = null, val = 3 };
var t = new TreeNode { left = k, right = p, val = 2 };
var d = new TreeNode { left = null, right = null, val = 5 };
var g = new TreeNode { left = null, right = null, val = 7 };
var s = new TreeNode { left = d, right = g, val = 6 };
var root = new TreeNode { left = t, right = s, val = 4 };
var listHeadNode = Func(root);
Console.WriteLine(listHeadNode.val);
}
public static ListNode Func( TreeNode node, Dictionary<string, ListNode> dic = null! ) {
if ( dic == null ) {
dic = new Dictionary<string, ListNode> { { "head", null! }, { "prev", null! } };
}
if ( node == null ) {
return dic[ "head" ];
}
var listNodeCurr = new ListNode { val = node.val };
Func( node.left, dic);
if (dic["prev"] == null) {
dic["head"] = listNodeCurr;
} else {
dic["prev"].next = listNodeCurr;
}
listNodeCurr.prev = dic["prev"];
dic["prev"] = listNodeCurr;
Func(node.right, dic);
return dic["head"];
}
```

- Scott January 12, 2015