Print all paths with given sum in binary tree - Java

Program:

Call Method:

int[] arr = new int[heightTree(root)];

printAllPaths(root, arr, 0, sum);

Better approach:

Connect nodes at same level - Java

Example

Input Tree
       A
      / \
     B   C
    / \   \
   D   E   F


Output Tree
       A---> NULL
      / \
     B--> C--> NULL
    / \   \
   D--> E--> F--> NULL

Method 1 (Extend Level Order Traversal or BFS)

Connect nodes at same level using constant extra space:

Tournament Tree (Winner Tree) and Binary Heap

Reference:

http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/

Check if a given Binary Tree is SumTree - Java

Program:

Reference:
http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/

Double Tree

Write a program that converts a given tree to its Double tree. To create Double tree of the given tree, create a new duplicate for each node, and insert the duplicate as the left child of the original node.
So the tree…

    2
   / \
  1   3

is changed to…

       2
      / \
     2   3
    /   /
   1   3
  /
 1

And the tree

            1
          /   \
        2      3
      /  \
    4     5

is changed to

               1
             /   \
           1      3
          /      /
        2       3
      /  \
     2    5
    /    /
   4   5
  /   
 4    

Program:

Reference:

http://www.geeksforgeeks.org/double-tree/

Root to leaf path sum equal to a given number

Idea:

- First check base conditions as per arguments passed in function.
- Take a subsum as a local variable for per stack which substracts the previous node values.
- check if node is leaf and subsum equals to zero then return true.
- if we find above condition true in any call then it has DONE and return true for each calls.


Program:

Inorder Tree Traversal without recursion and without stack in java

Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.

Program :

Reference:
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

Convert an arbitrary Binary Tree to a tree that holds Children Sum Property

Question: Given an arbitrary binary tree, convert it to a binary tree that holds Children Sum Property. You can only increment data values in any node (You cannot change structure of tree and cannot decrement value of any node).

For example, the below tree doesn’t hold the children sum property, convert it to a tree that holds the property.

             50
           /     \     
         /         \
       7             2
     / \             /\
   /     \          /   \
  3        5      1      30

Now convert the root, we have to increment left subtree for converting the root.

          50
        /    \     
      /        \
    19           31
   / \           /  \
 /     \       /      \
14      5     1       30

Java Implementation:

static void convertMaxSumTree(Node root){
  
  if(root == null || (root.left == null && root.right == null)) return;
  
  int sum = 0 ;
  
  convertMaxSumTree(root.left);
  
  convertMaxSumTree(root.right);
  
  if(root.left != null){
   sum += root.left.data;
  }
  
  if(root.right != null)
   sum += root.right.data;
  
  int diff = sum - root.data;
  
  if(diff > 0){
   root.data += diff;
  }else if(diff < 0){
   increaseValue(root, -diff);
  }
  
  
 }
 
 private static void increaseValue(Node root, int diff) {

  //if(root == null) return;
  
  if(root.left != null)
  {
   root.left.data += diff;
   increaseValue(root.left, diff);
  }else if(root.right != null)
  {
   root.right.data += diff;
   increaseValue(root.right, diff);
  }
 }

 

Transform a BST to greater sum tree

Given a BST, transform it into greater sum tree where each node contains sum of all nodes greater than that node.

Program:

 static void transformBSTSumTree(Node root){
  
  if(root == null) return;
  
  transformBSTSumTreeUtil(root, 0);
  //System.out.println("Sum of BST: "+r);
 }
 
 
 

 private static int transformBSTSumTreeUtil(Node root, int max_sum) {

  if(root == null) return 0;
  
  int r = transformBSTSumTreeUtil(root.right, max_sum);
  
  max_sum = max_sum + r;
  int tmp = root.data;
  root.data = max_sum;
  max_sum = max_sum + tmp;
  
  int l = transformBSTSumTreeUtil(root.left, max_sum);
  
  return l+r+tmp;
  
 }

Print all path from its root to leaf Node in one per line

Algorithm:

Initialize: array of size equal to height of BT. let say arr[height()]
/*height of tree is equal to max number of levels in tree*/

Call Method with signature:
  int[] arr = new int[height()];
  printAllPath(root, arr, 0);
/*printPathsRecur traverses nodes of tree in preorder */
printPathsRecur(tree, path[], level)
1) If node is null then return;
push data to path array: arr[level] = node->data.
2) If node is a leaf node then print the path array. return;
3)   a) Call printPathsRecur for left subtree
                 printPathsRecur(node->left, path, level+1)
     b) Call printPathsRecur for right subtree.
                printPathsRecur(node->right, path, level+1)

Example:

 static void printAllPath(Node root, int[] arr, int level){
  
  if(root == null) return;
  
  arr[level] = root.data;
  
  if(root.left == null && root.right == null)
  {
   printPath(arr, 0, level);
   return;
  }
  
  printAllPath(root.left, arr, level+1);
  printAllPath(root.right, arr, level+1);
  
 }

 private static void printPath(int[] arr, int l, int level) {

  for(int i = l; i <= level; i++)
   System.out.print(arr[i]+", ");
  System.out.println();
  
 }

Construct-tree-from-given-inorder-and-preorder-traversal

Program:

 private static int p = 0;
 
 static Node buildTree(int[] in, int[] pre) throws Exception{
  
  int l1 = in.length;
  int l2 = pre.length;
  
  if(l1 != l2) throw new Exception("\nImpossible to build tree.\n");
  
  return buildTreeUtil(in, pre, 0, l1-1);
  
 } 

 private static Node buildTreeUtil(int[] in, int[] pre, int l, int r) throws Exception {
  
  if(l > r) return null;
  
  Node root = new Node(pre[p]);

  int pos = searchKey(in, pre[p], l, r);
  
  if(pos == -1) throw new Exception("\n Impossible to build tree. Key doesn't exist.");
  
  p++;
  
  if(l == r) return root;
  
  root.left = buildTreeUtil(in, pre, l, pos-1);
  
  root.right = buildTreeUtil(in, pre, pos+1, r);
  
  return root;
 }

 private static int searchKey(int[] in, int key, int l, int r) {

  for(int i = l; i <= r; i++)
  {
   if(in[i] == key) return i;
  }
  return -1;
 }

Reference:

http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

Print a Binary Tree in Vertical Order

Traversal of tree with level and HashMap>

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

HashMap> map = new HashMap>();

printVerticalOrderUtil(root, 0, map);

for(Integer level: map.keySet()){
ArrayList tmp = map.get(level);

for(Integer value: tmp)
System.out.print(value + ",");
System.out.println();
}
System.out.println();
}

private static void printVerticalOrderUtil(Node root, int level,
HashMap> map) {

if(root == null) return;

ArrayList list = (map.get(level) != null)? map.get(level): new ArrayList();
list.add(root.val);

map.put(level, list);

printVerticalOrderUtil(root.left, level-1, map);

printVerticalOrderUtil(root.right, level+1, map);


}


Reference:
http://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/

Given a binary tree, print its perimeter.

node, left->most nodes from top to bottom, leaf nodes from left-> right, right->most nodes from bottom to top 

----------------------------1
                                 /   \
----------------------- 2       3 
                           /   \       /  \
-----------------4-----  5---6---7 
                    /   \            /     /  \
-------------8------9-----10---11--12 

should print: 
1-2-4-8-9-5-10-11-12-7-3 

5 because it doesn't have any children. 10 and 11 are children of 6 and 8 & 9 are children of 4. 



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

perimeterTraversalUtil(root,true,true);
}


private static void perimeterTraversalUtil(Node root, boolean isLeft, boolean isRight){

if(root == null) return;

if(isLeft || root.left == null && root.right == null)
{
System.out.print(root.val+"->");
}

perimeterTraversalUtil(root.left, isLeft?true:false, false);

perimeterTraversalUtil(root.right, false, isRight?true:false);

if(isRight  && !isLeft && !(root.left == null && root.right == null))
{
System.out.print(root.val+"->");
}

}

Find deepest common ancestor in BST

Conditions for finding ca in bst:
        9
      /
    5
   /  \
3     8

3,8 ca is 5
5,3 ca is 9


static Node findDeepeastCommonAncestor(Node root, int d1, int d2){
if(root == null) return null;

if(!search(root, d1) || !search(root, d2)) return null;

if(d1 > d2)
{
int tmp = d1;
d1 = d2;
d2 = tmp;
}

return findDeepeastCommonAncestorUtil(root, d1, d2);
}

private static Node findDeepeastCommonAncestorUtil(Node root, int d1, int d2){
if(root == null) return null;

if(root.val > d1 && root.val < d2) return root;

if(root.val > d1 && root.val > d2)
{
if(root.left != null && root.left.val == d1) return root;

return findDeepeastCommonAncestorUtil(root.left, d1, d2);
}

if(root.val < d1 && root.val < d2)
{
if(root.right != null && root.right.val == d1) return root;

return findDeepeastCommonAncestorUtil(root.right, d1, d2);
}

return null;
}


private static boolean search(Node root, int data) {

if(root == null) return false;

if(root.val == data) return true;

if(root.val > data) return search(root.left, data);
return search(root.right, data);
}

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/

Create a mirror of a binary tree

http://www.geeksforgeeks.org/write-an-efficient-c-function-to-convert-a-tree-into-its-mirror-tree/
http://geekyjumps.blogspot.in/2013/09/create-mirror-of-binary-tree.html

Algorithm - Mirror(tree):

(1)  Call Mirror for left-subtree i.e., Mirror(left-subtree)
(2)  Call Mirror for right-subtree i.e., Mirror(left-subtree)
(3)  Swap left and right subtrees.
          temp = left-subtree
          left-subtree = right-subtree
          right-subtree = temp

Program- Mirror(tree):

 public static void mirrorTree(Node root){
  if(root == null) return;
  
  Node tmp = root.left;
  root.left = root.right;
  root.right = tmp;
  
  mirrorTree(root.left);
  mirrorTree(root.right);
 }

static Node mirrorBT(Node root)
{

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

if(root.left == null && root.right == null) return root;

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

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

Node leftTree = mirrorBT(root.left);
Node rightTree = mirrorBT(root.right);

// swap the child nodes of root
root.left = rightTree;
root.right = leftTree;

return root;

  }

LCA of two given tree nodes

Solution:
There’s only three cases i need to consider.

1. Both nodes are to the left of the tree.
2. Both nodes are to the right of the tree.
3. One node is on the left while the other is on the right.

static Node lcaOfTwoNodes(Node root, Node x, Node y)
{
if(root == null || x == null || y == null ) return null;

if (root.data >= x.data && root.data <= y.data)
{
return root;
}

if(root.data > y.data)
{
Node result = lcaOfTwoNodes(root.left, x, y);
if(result != null)
{
return result;
}
}else{
return lcaOfTwoNodes(root.right, x, y);
}
return null;
}

Distance between two nodes of binary tree

static int distanceOfTwoNodes(Node root, Node x, Node y)
{
if(root == null) return 0;

int l = distanceOfTwoNodes(root.left, x, y);
int r = distanceOfTwoNodes(root.right, x, y);

if(l != 0 || r != 0) return (l+r+1);
if(root.data == x.data || root.data == y.data) return 1;


return 0;
}

Vertical Sum in a given Binary Tree

http://www.geeksforgeeks.org/vertical-sum-in-a-given-binary-tree/

static void verticalSum(Node root) {
if (root == null)
return;
int hd = 0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

verticalSumWrapper(root, hd, map);
if (map != null) {
System.out.println(map.entrySet());
}
}

static void verticalSumWrapper(Node root, int hd, HashMap<Integer, Integer> mp) {
if (root == null)
return;

int tmp = (mp.get(hd) == null) ? 0 : (mp.get(hd));
tmp = tmp + root.data;
mp.put(hd, tmp);

verticalSumWrapper(root.left, hd - 1, mp);

verticalSumWrapper(root.right, hd + 1, mp);

}