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

}