import java.util.Stack;
/*
* Given Tree and Node n and int k, print all node which are at physical
distance <=k from n
* @Amazon intern
*/
public class Solution {
public static void main(String args[]){
Solution solution = new Solution();
TreeNode a = new TreeNode(8);
TreeNode b = new TreeNode(6);
TreeNode c = new TreeNode(10);
TreeNode d = new TreeNode(9);
TreeNode e = new TreeNode(12);
TreeNode f = new TreeNode(4);
TreeNode g = new TreeNode(7);
TreeNode h = new TreeNode(3);
TreeNode i = new TreeNode(5);
a.left = b;
a.right = c;
c.left = d;
c.right = e;
b.left = f;
b.right = g;
f.left = h;
f.right = i;
solution.displayTree(a);
for (int k = 0; k < 13; k++) {
System.out.println(k + " closest nodes to root = 8 include: ");
solution.printkdistanceNodeDown(a, k);
System.out.println(k + " closest nodes to c = 10 include: ");
solution.printkdistanceNodeDown(a, c, k);
System.out.println(k + " closest nodes to i = 5 include: ");
solution.printkdistanceNodeDown(a, i, k);
System.out.println("--------------------------");
}
}
/* Recursive function to print all the nodes at distance k in the
tree (or subtree) rooted with given root. See */
public void printkdistanceNodeDown(TreeNode root, int k) {
// Base Case
if (root == null || k < 0)
return;
// If we reach a k distant node, print it
if (k >= 0)
System.out.println(root.val);
// Recur for left and right subtrees
printkdistanceNodeDown(root.left, k - 1);
printkdistanceNodeDown(root.right, k - 1);
}
// Prints all nodes at distance k from a given target node.
// The k distant nodes may be upward or downward. This function
// Returns distance of root from target node, it returns -1 if target
// node is not present in tree rooted with root.
public int printkdistanceNodeDown(TreeNode root, TreeNode target, int k)
{
// Base Case 1: If tree is empty, return -1
if (root == null)
return -1;
// If target is same as root. Use the downward function
// to print all nodes at distance k in subtree rooted with
// target or root
if (root == target) {
printkdistanceNodeDown(root, k);
return 0;
}
// Recur for left subtree
int dl = printkdistanceNodeDown(root.left, target, k);
// Check if target node was found in left subtree
if (dl != -1) {
// If root is at distance k from target, print root
// Note that dl is Distance of root's left child from target
if (dl + 1 <= k)
System.out.println(root.val);
// Else go to right subtree and print all k-dl-2 distant nodes
// Note that the right child is 2 edges away from left child
else
printkdistanceNodeDown(root.right, k - dl - 2);
// Add 1 to the distance and return value for parent calls
return 1 + dl;
}
// MIRROR OF ABOVE CODE FOR RIGHT SUBTREE
// Note that we reach here only when node was not found in left
subtree
int dr = printkdistanceNodeDown(root.right, target, k);
if (dr != -1) {
if (dr + 1 <= k)
System.out.println(root.val);
else
printkdistanceNodeDown(root.left, k - dr - 2);
return 1 + dr;
}
// If target was neither present in left nor in right subtree
return -1;
}
public TreeNode sortedArrayToBST(int num[]) {
if(num.length==0) return null;
return rec(num, 0, num.length - 1);
}
private TreeNode rec(int num[], int start, int end) {
if (start > end)
return null;
int mid = (start + end) / 2;
TreeNode node = new TreeNode(num[mid]);
node.left = rec(num, start, mid - 1);
node.right = rec(num, mid + 1, end);
return node;
}
public void displayTree(TreeNode node) {
Stack globalStack = new Stack();
globalStack.push(node);
int nBlanks = 40;
boolean isRowEmpty = false;
System.out
.println("\n................................................
......");
while (isRowEmpty == false) {
Stack localStack = new Stack();
isRowEmpty = true;
for (int j = 0; j < nBlanks; j++)
System.out.print(' ');
while (globalStack.isEmpty() == false) {
TreeNode temp = (TreeNode) globalStack.pop();
if (temp != null) {
System.out.print(temp.val);
localStack.push(temp.left);
localStack.push(temp.right);
if (temp.left != null || temp.right != null)
isRowEmpty = false;
} else {
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for (int j = 0; j < nBlanks * 2 - 2; j++)
System.out.print(' ');
} // end while globalStack not empty
System.out.println();
nBlanks /= 2;
while (localStack.isEmpty() == false)
globalStack.push(localStack.pop());
} // end while isRowEmpty is false
System.out.println("................................................
......");
}
}
