Given a Binary Tree (or BST).
1. Flatten the BT into a single link in the order of inorder traversal.
2. Flatten the BT into a single link in the order of preorder traversal.
3. Flatten the BST to sorted single linked list.
4. Flatten a BST to Double Linked List
5. Flatten a BST to Circular Double Linked List
6. Convert Sorted Linked List to BST.
7. Convert heap ordered Linked List to BT.

What if we are given a linked list (or sorted list for BST) and we want to convert to a Binary Tree (or BST)? Can we do the same in pre-order traversal order.

Explain how we can do these iteratively and/or in-place?

For example,

      6
    /   \
   4     8
  / \     \
 1  5     11
         / 
       10

Then the single linked list would be : 1 -> 4 -> 5 -> 6 -> 8 -> 10 -> 11-> null.

2-3. What if we need it in pre-order inplace ? For example,

should be converted to

4-5. In case we need a circular DLL the output should be

->1 <-> 4 <-> 5 <-> 6 <-> 8 <-> 10 <-> 11<- \ 
\____________________________________________\

6. If we are given a sorted linked list 1 -> 4 -> 5 -> 6 -> 8 -> 10 -> 11-> null then we want to convert it to a binary search tree as follows –

      6
    /   \
   4     8
  / \     \
 1  5     11
         / 
       10

7. If we are given a linked list that contains nodes in heap order such as 1 -> 4 -> 5 -> 6 -> 8 -> 10 -> 11-> null then we want to convert it to a balanced binary tree as follows –

      1
    /   \
   4      5
  / \    / \
 6   8  10 11

Convert Binary Tree to Single Linked List

Converting BT to SLL is straightforward because we can traverse the tree inorder and keep appending the nodes into a linked list. We can either do this recursively or iteratively. Doing iterative manner using a stack to perform inorder traversal is easier to manipulate the resulting list. I will discuss recursive solution in this post which requires some extra efforts to understand.

public static void flattenBT2SLLFaster(BTNode root, LinkedList<BTNode> head){
	if(root == null){
		return ;
	}
	
	flattenBT2SLLFaster(root.left, head);
	head.add(root);
	flattenBT2SLLFaster(root.right, head);
}

Iterative in-place – using stack
How can we do it in-place without using any extra data structure to contain the list? Note that, once we traverse a node it’s left and right pointers are no more needed for the rest of traversal. So, we could potentially reuse these pointers to create the next (and prev) pointers of linked list. For example, we could use right pointer as the next pointer in flattened linked list. This code runs in O(n) time and uses O(n) space.

public static BTNode inorderInPlaceUsingStack(BTNode root){
	
	Stack<BTNode> stack = new Stack<test.BTNode>();
	BTNode cur = root;
	BTNode head =  null;
	BTNode iterator = null;
	
	while(true){
		if(cur != null){
			stack.push(cur);
			cur = cur.left;
		}
		else{
			if(stack.isEmpty()){
				return head;
			}
			else{
				cur = stack.pop();
				if(head == null){
					head = cur;
					iterator = head;
				}
				else if(iterator != null){
					iterator.right = cur;
					iterator = iterator.right; 
				}
				cur = cur.right;
			}
		}
	}
}

How we can do better? with constant space?
We can traverse the tree in any order without recursion stack or explicit stack i.e. in constant space. I discussed in my previous post about Morris Inorder Traversal with constant space. We can use the same traversal mechanism and append the visited nodes along the way. Below is the implementation in O(n) and O(1) extra space (not counting space required for returned linked list). We will later discuss how to do it in-place.

public static BTNode convertToListInplace(BTNode root){
	if(root == null){
		return null;
	}
	BTNode iterator = null;
	BTNode head = null;
	BTNode cur = root;
	BTNode pre = null;
	while(cur != null){
		//if no left subtree the visit right subtree right away after printing current node
		if(cur.left == null){
			if(head == null){
				head = cur;
				iterator = head;
			}
			else{
				iterator.right = cur;
				iterator = iterator.right;
			}
			System.out.print(cur.key+", ");
			cur = cur.right;
		}
		else{
			//otherwise we will traverse the left subtree and come back to current 
			//node by using threaded pointer from predecessor of current node 
			//first find the predecessor of cur
			pre = cur.left;
			while(pre.right != null && pre.right != cur){
				pre = pre.right;
			}
			
			//threaded pointer not added - add it and go to left subtree to traverse
			if(pre.right == null){
				pre.right = cur;
				cur = cur.left;
			}
			else{
				//we traversed left subtree through threaded pointer and reached cur again
				//so revert the threaded pointer and print out current node before traversing right subtree
				pre.right = null;
				if(head == null){
					head = cur;
					iterator = head;
				}
				else{
					iterator.right = cur;
					iterator = iterator.right;
				}
				System.out.print(cur.key+", ");
				//now traverse right subtree
				cur = cur.right;
			}
		}
	}
	
	return head;
}

Convert Binary Tree to Single Linked List preorder in-place

First of all let’s think How can we do it inplace, without using any extra data structure. Notice that tree already have two pointers left and right. Once we traverse a node and find its children then left and right pointers will not be needed anymore for traversal. So, we can reuse these pointers for linked list’s prev/next pointers. Let’s do it for pre-order traversal.

We can formulate a recursive solution to traverse root and then flatten left subtree and then flatten right subtree and then merge them together through their right pointer. We can also do this in iterative manner using a stack. starting from root –

if it has left subtree, store the right subtree (if not null) to stack, move the left subtree to right
if not, append back a subtree from stack to the current node’s right
continue to the right node until finish.

But how we can do this with constant space? Yes, we can do constant space by traversing the tree in iterative manner using only two pointers. Each time we prune a right subtree, we loop to find the predecessor of current node i.e. the right-most leaf of the current left subtree, and append the subtree there. Below is an implementation of the above idea in Java in O(n) time and O(1) space.

//The idea of inplace is to use tree's left and right pointer to connect linked list nodes
//It is possible because once we visit childs of a node we don't actually need left/right 
//pointers anymore. So, we can reuse them for pointing prev/next nodes.
public static void flattenBT2LLPreOrderInplace(BTNode root){
	if(root == null){
		return;
	}
	
	BTNode cur = root;
	while(cur != null){
		//if cur has a left child then we would like to flatten the left subtree recursively
		//and put then under right child of cur so that we get a flatten list by right pointer to traverse
		//We put left subtree first and then right subtree
		if(cur.left != null){
			//As we will put flattened left subtree to the right pointer of cur so
			//before doing that we need to point the last (rightmost) node of flattened left subtree
			//to point to right subtree (if it exists)
			if(cur.right != null){
				BTNode last = cur.left;
				while(last.right != null){
					last = last.right;
				}
				
				last.right = cur.right;
			}
			
			//now update next (right) pointer of cur node to flattened left subtree
			cur.right = cur.left;
			cur.left = null;//Single Linked list - so no prev pointer
		}
		//if thers is no left subtree the we directly go to right subtree and flatten it out
		else{
			cur = cur.right;
		}
	}
}

We visit each node at most twice (one for flattening and maybe one for looking for rightmost leaf) and then for each node, cut the right tree and append it to its rightmost node. Overall, we access each node constant time. So the total running time is O(n) with O(1) space.

Convert Binary Tree to Double Linked List – inplace

As we discussed earlier we can reuse left and right pointers to connect link list nodes so, we can create DLL by doing inorder traversal and connecting nodes by their left and right nodes along the traversal path.

1. If left subtree exists, process the left subtree
     i) Recursively convert the left subtree to DLL.
    ii) Connect left subtree DLL to root. So, we will need connect inorder predecessor of the root to the root.
2. If right subtree exists, process the right subtree.
     i) Recursively convert the right subtree to DLL.
     ii) Connect root to right subtree DLL. So, we will need connect root to inorder successor of the root.
3. return the left as it is the head of the DLL.

public static BTNode flattenBST2SortedDLLInplace(BTNode root){
	if(root == null){
		return null;
	}
	
	//convert left subtree to DLL and connect last node (=predecessor of current root) to current root 
	if(root.left != null){
		//convert left subtree
		BTNode left = flattenBST2SortedDLLInplace(root.left);
		
		//find last node of the left DLL
		while(left.right != null){
			left = left.right;
		}
		
		//connect left DLL to root
		left.right = root;
		root.left = left;
	}
	//convert right subtree to DLL and connect root to the first node (=successor of current root)
	if(root.right != null){
		//convert left subtree
		BTNode right = flattenBST2SortedDLLInplace(root.right);
		
		//find first node of the right DLL
		while(right.left != null){
			right = right.left;
		}
		
		//connect left DLL to root
		right.left = root;
		root.right = right;
	}
	
	return root;
}

Convert Binary Tree to Double Circular Linked List – inplace
How to make the DLL circular? Trivial solution would be to just connect left most node to the right most node of the DLL we found at previous step. This requires additional O(n) scan to find the right most node. However we can do better.

The idea is that when we connect two nodes, we will connect them in circular manner. For example, a single node can be transformed to a double circular linked list by pointing its left and right pointer back to itself.

Now, next question is how to connect two circular list? Let’s take an example – how to concat B to the end of A?

A                             B
---                           __

->1 <-> 4 <-> 5 <-\           ->6 <-> 8 <-> 10 <-> 11 <-\ 
\__________________\          \__________________________\


->1 <-> 4 <-> 5 <-> 6 <-> 8 <-> 10 <-> 11<- \ 
\____________________________________________\


disconnect(1, 5);
disconnect(6, 11);
connect(5, 6);
connect(1, 11);

So, in order to concat two circular lists we need to –

join tail1 and head2 to append list2 to at the end of list1
join tail2 and head1 to make it circular

How do we join two nodes? simply connect their left and right pointers. So, let’s get back to original problem where we wanted to convert BT to circular DLL. The idea is same as before –

1. recursively divide it into left and right subtree until we get a leaf node which can be a stand alone doubly circular linked list by doing some simple pointer manipulation
2. Convert the root node into a stand alone circular DLL - just make it a self loop
3. We have now sublist on the left of root and sublist on the right of root. So, we just need to append left, root, and right sublists in the respective order

Below is an implementation of this very efficient both in time and space. Tie complexity is O(n) and space complexity is O(1).

public static BTNode flattenBST2SortedCircularDLLInplace(BTNode root){
	if(root == null){
		return null;
	}
	
	//recursively divide it into left and right subtree until we get a leaf node which 
	//can be a stand alone doubly circular linked list by doing some simple pointer manipulation
	BTNode left = flattenBST2SortedCircularDLLInplace(root.left);
	BTNode right = flattenBST2SortedCircularDLLInplace(root.right);
	
	//Let's first convert the root node into a stand alone circular DLL - just make it a self loop
	root.right = root;
	root.left = root;
	
	//We have now sublist on the left of root and sublist on the right of root.
	//So, we just need to append left, root, and right sublists in the respective order
	left = concatCircularDLL(left, root);
	left = concatCircularDLL(left, right);
	
	return left;
}

public static void joinCircularNodes(BTNode node1, BTNode node2){
	node1.right = node2;
	node2.left = node1;
}

//concats head2 list to the end of head1 list
public static BTNode concatCircularDLL(BTNode head1, BTNode head2){
	if(head1 == null){
		return head2;
	}
	if(head2 == null){
		return head1;
	}
	//in order to concat two circular list we need to
	//1. join tail1 and head2 to append list2 to at the end of list1
	//2. join tail2 and head1 to make it circular
	BTNode tail1 = head1.left;
	BTNode tail2 = head2.left;
	
	//join tail1 and head2 to append list2 to at the end of list1
	joinCircularNodes(tail1, head2);
	//join tail2 and head1 to make it circular
	joinCircularNodes(tail2, head1);
	
	return head1;
}

Convert a Sorted Single/Double Linked List to BST
If we had given a sorted array then how would we construct a BST from the array? Ofcourse dividing the array repeatedly by half around the middle element and convert left half to left subtree and right half to right subtree and make them subtree of middle element. Now, we need to do this for linked list.

There is a challenge however – We can’t directly access to middle element (root) in the list without traversing them. We can easily solve this by doing recursion with passing start and end index of elements of the list should we traverse for left subtree. The next element would be the middle element.

1. Build left subtree from List[start to mid-1]
2. Build root node from middle element List[middle]
3. Set left of root to left subtree we found.
4. Increment head of list to point next element.
5. Build right subtree from List[mid+1 to end]
6. Set right of root to right subtree found.

We can do this in a simple recursion. There is one small challenge however – how to increment head pointer? head = head.next would work in recursion? It will in C++ because C++ passes object by reference. Java passes objects by value of the reference, so if we do head=head.next it is just changing the value of reference (i.e. memory address of head is changing). But head will still be holding same value as old. So we can’t just do h = h.next. Instead we can update the head by value of head.next and update it’s prev/next pointer manually. Below is the implementation of the above idea which takes O(n) time and O(n) space for linked list.

//works for sorted/unsorted single/double linked list and for both BT and BST
public static BTNode convertList2BTreeRecursive(ListNode h, int start, int end){
	if(start > end){
		return null;
	}
	
	//keep halving
	int mid = (start)+(end-start)/2;
	
	//build left subtree
	BTNode left = convertList2BTreeRecursive(h, start, mid-1);
	//build root from current node
	BTNode root = new BTNode(h.val);
	//update left
	root.left = left;
	//build right subtree - first we need to increment head pointer 
	//java pass objects by reference , so we can't just do h = h.next
	//instead we can update the head by value of head.next
	//head = head.next;
	if(h.next != null){
		h.val = h.next.val;
		h.next = h.next.next;
		root.right = convertList2BTreeRecursive(h, mid+1, end);
	}
	
	return root;
}

Convert a Sorted/Unsorted Double Linked List to Binary Tree (or BST) – inplace
How can we do it in place so that we can do it in constant space? By reusing prev and next pointer. Below is the straightforward translation of the previous code where we are reusing prev and next pointer of current node as the left and right pointer of the transformed tree node.

public static ListNode convertList2BTreeInplace(ListNode head){
	int n = 0;
	ListNode temp = head;
	while(temp != null){
		n++;
		temp = temp.next;
	}
	
	return convertList2BTreeInplace(head, 0, n-1);
}

//works in place for sorted/unsorted single/double linked list and for both BT and BST
public static ListNode convertList2BTreeInplace(ListNode h, int start, int end){
	if(start > end){
		return null;
	}
	
	//keep halving
	int mid = (start)+(end-start)/2;
	
	//build left subtree
	ListNode left = convertList2BTreeInplace(h, start, mid-1);
	//build root from current node
	ListNode root = new ListNode(h.val);//h;
	//update left
	root.prev = left;
	//build right subtree - first we need to increment head pointer 
	//java pass objects by reference , so we can't just do h = h.next
	//instead we can update the head by value of head.next
	//head = head.next;
	if(h.next != null){
		h.val = h.next.val;
		h.next = h.next.next;
		root.next = convertList2BTreeInplace(h, mid+1, end);
	}
	
	return root;
}

Convert a Linked List Heap to BT
What if we had given a list that stores the BT in heap order? So, (2*i+1)th element would be left child and (2*i+2)th element would be right child of ith element. How can we convert it to BT?

We can use a queue and for each popped element starting from root (head of the list) we take next two elements from the list. They are respectively left and right nodes of current popped element. Then we can push left and right nodes to process the subtrees.

public static BTNode convertList2BTreeIterative(ListNode head){
	if(head == null){
		return null;
	}
	Queue<BTNode> queue = new LinkedList<BTNode>();
	BTNode root = new BTNode(head.val);
	head = head.next;
	queue.offer(root);
	
	BTNode node = null;
	while(!queue.isEmpty()){
		node = queue.poll();
		if(head != null){
			node.left = new BTNode(head.val);
			head = head.next;
			queue.offer(node.left);
		}
		if(head != null){
			node.right = new BTNode(head.val);
			head = head.next;
			queue.offer(node.right);
		}
	}
	
	return root;
}

Algorithms

Transformation between Binary Tree and Linked Lists

Leave a Reply Cancel reply

Leave a Reply Cancel reply

Login