Convert Binary Search Tree (BST) to Sorted Doubly-Linked List

Solution: 
When I first see this problem, my first thought was in-order traversal. Couldn’t we modify the nodes’ left and right pointers as we do an in-order traversal of the tree? However, we have to beware not to modify the pointers and accessing it at a later time.

As we traverse the tree in-order, we could safely modify a node’s left pointer to point to the previously traversed node as we never use it once we reach a node. We would also need to modify the previously traversed node’s right pointer to point to the current node. Note: The previously traversed node meant here is not its parent node. It is the node’s previous smaller element.

Easy approach, right? But wait, we are still missing two more steps. First, we did not assign the list’s head pointer. Second, the last element’s right pointer does not point to the first element (similar to the first element’s left pointer).

How do we solve this? My approach is pretty easy: Just update the current node’s right pointer to point back to the head and the head’s left pointer to point to current node in each recursive call. As the recursion ends, the list’s head and tail would be automagically updated with the correct pointers. Don’t forget to check for this special case: A list with only one element should have its left and right pointers both pointing back to itself.

A double-linked list with a length of one.

Do you think this approach works? I bet it did! The run time complexity for this solution is O(N) since we are essentially doing a modified in-order traversal. It does have some extra assignments in each recursive call though. But overall I am quite satisfied with this approach because it is intuitive and easy to follow. Besides, we are adapting an existing algorithm (in-order traversal) to solve this problem, isn’t this just neat?

Program:

 static Node previous = null, headList = null;
 static void treeToList(Node root){
  
  if(root == null) return;
  
  if(previous == null && root.left == null && root.right == null)
  {
   headList = previous = root;
   return;
  }
  
  treeToList(root.left);
  
  previous.right = root;
  root.left = previous;
  
  previous = root;
  Node tmp = root.right;
  
  headList.left = root;
  root.right = headList;
  
  treeToList(tmp);
  
 }

References:
http://leetcode.com/2010/11/convert-binary-search-tree-bst-to.html


or


private static Node convert2DLLUtil(Node root){

if(root == null) return null;

if(root.left != null)
{
Node left = convert2DLLUtil(root.left);

for( ; left.right != null; left = left.right);

left.right = root;
root.left = left;
}

if(root.right != null)
{
Node right = convert2DLLUtil(root.right);

for( ; right.left != null; right = right.left);

right.left = root;
root.right = right;
}

return root;
}


static Node convert2DLL(Node root){
if(root == null) return null;

Node tmp = convert2DLLUtil(root);

for( ;tmp.left != null; tmp = tmp.left);

return tmp;


}

Reference:
http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/

Printing a Binary Tree in Zig Zag Level-Order

Solution:
This problem can be solved easily using two stacks (one called currentLevel and the other one called nextLevel). You would also need a variable to keep track of the current level’s order (whether it is left->right or right->left).

You pop from stack currentLevel and print the node’s value. Whenever the current level’s order is from left->right, you push the node’s left child, then its right child to stack nextLevel. Remember a Stack is a Last In First OUT (LIFO) structure, so the next time when nodes are popped off nextLevel, it will be in the reverse order.

On the other hand, when the current level’s order is from right->left, you would push the node’s right child first, then its left child. Finally, don’t forget to swap those two stacks at the end of each level (ie, when currentLevel is empty).

static void zigzagTraversal(Node root){
if(root == null) return;

Stack<Node> currLevel, nextLevel = null;
currLevel = new Stack<Node>();
nextLevel = new Stack<Node>();

currLevel.push(root);
boolean lefttoright = true;

while(!currLevel.isEmpty())
{
Node currNode = currLevel.pop();
//System.out.print(currNode.val+" ");
if(currNode != null)
{
System.out.print(currNode.val+" ");
if(lefttoright){
if(currNode.left != null)
nextLevel.push(currNode.left);
if(currNode.right != null)
nextLevel.push(currNode.right);
}else{
if(currNode.right != null)
nextLevel.push(currNode.right);
if(currNode.left != null)
nextLevel.push(currNode.left);
}
}
if(currLevel.isEmpty())
{
System.out.println();
lefttoright = !lefttoright;
Stack<Node> tmp = currLevel;
currLevel = nextLevel;
nextLevel = tmp;
}
}

}


References:
http://leetcode.com/2010/09/printing-binary-tree-in-zig-zag-level_18.html

Find rightmost elements at each level of binary tree

// - Find height(h) of binary tree and define the array of size h.
// - Traverse the binary tree and store the elements of each level at the array index of level

static void rightSideElements(Node root){

int level = 0;
int h = heightBT(root);
int arr[] = new int[h];
rightSideUtil(root, level, arr);
for(int i = 0; i<arr.length; i++)
{
System.out.print(arr[i]+", ");
}
}

private static void rightSideUtil(Node root, int level, int[] a){

if(root == null) return;

a[level] = root.data;

rightSideUtil(root.left, level+1, a);
rightSideUtil(root.right, level+1, a);

}

Print all nodes that are at distance k from a leaf node

// function to calculate height of binary tree that is used to define the lenght of ancestor path array and boolean array.
private static int heightBT(Node root){
if(root == null) return 0;
int l = heightBT(root.left);
int r = heightBT(root.right);
return ((l>r)?l:r) + 1;
}

private static void allNodesfromLeafUtil(Node root, int k, int path[], int visited[], int pathlen){
if(root == null) return;
// keep storing all ancestors till we hit a leaf node also keep tracking the nodes that are already printed for that we use a boolean array visited[].
path[pathlen] = root.data;
visited[pathlen] = 0;
pathlen++;

if(root.left == null && root.right == null && pathlen-k-1 >= 0 && visited[pathlen-k-1] == 0)
{
System.out.println(path[pathlen-k-1]);
visited[pathlen-k-1] = 1;
return;
}

allNodesfromLeafUtil(root.left, k, path, visited, pathlen);
allNodesfromLeafUtil(root.right, k, path, visited, pathlen);
}

static void allNodesfromLeaf(Node root, int k){
int pathlen = 0;
int height = heightBT(root);
int path[] = new int[height];
int visited[] = new int[height];
allNodesfromLeafUtil(root, k, path, visited, pathlen);
}

Find distance between two given keys of a Binary Tree

//  Instance variable distance to store the final distance b/w two nodes:

private static int distance = -1;

private static int distTwoNodesUtil(Node root, int n1, int n2){

                // Base condition:
                if(root == null) return 0;

int l = distTwoNodesUtil(root.left, n1, n2);
int r = distTwoNodesUtil(root.right, n1, n2);

                // if n1, n2 present at both side of  the root
if(l != 0 && r != 0)
{
distance = l+r;
}else if((l != 0 || r != 0) && ((root.data == n1) || (root.data == n2)))
{
distance = l+r;
}else if(l !=0 || r != 0)
{
return l+r+1;
}else if(root.data == n1 || root.data == n2)
{
return 1;
}

return 0;

}


static int distbwTwoNodes(Node root, int n1, int n2){
distTwoNodesUtil(root,n1,n2);
return distance;
}


References:

http://www.geeksforgeeks.org/find-distance-two-given-nodes/

Lowest Common Ancestor in a Binary Tree

private static int LCABTUtil(Node root, int n1, int n2)
{
              //Base Condition
if(root == null) return 0;

int l = LCABTUtil(root.left, n1, n2);
int r = LCABTUtil(root.right, n1, n2);

// Node that has both n1 and n2 as descendants
if((l == 1 && r == 1))
{
System.out.println(root.data);
}
              // If node to be a descendant of  itself
              else if((l == 1 || r == 1) && (root.data == n1 || root.data == n2))
{
System.out.println(root.data);
}
              // Node that has one of descendant
               else
{
if(l == 1 || r == 1)
{
return 1;
}
}

if(root.data == n1 || root.data == n2)
{
return 1;
}
return 0;
}


static void lcaBT(Node root, int n1, int n2)
{
LCABTUtil(root, n1, n2);
}



References:
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

Print all nodes that don’t have sibling

static void noOfSibblings(Node root, ArrayList<Integer> l){

//Base condition
if(root == null) return;

if(root.left != null && root.right == null)
{
l.add(root.left.data);
}else if(root.left == null && root.right != null)
{
l.add(root.right.data);
}

noOfSibblings(root.left,l);

noOfSibblings(root.right,l);
}


References:
http://www.geeksforgeeks.org/print-nodes-dont-sibling-binary-tree/