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);
}