Given a Binary Tree. Assuming each node denotes some x,y coordinate. root node denotes (0,0). Write a code to display coordinate of all nodes.
For example, let us consider the below tree:
Output: Coordinate of 4 : (0,0), Coordinate of 2 : (-1,-1), Coordinate of 3 : (1,-1), Coordinate of 1 : (-2,-2), Coordinate of 3 : (0,-2) etc.
Solution:
class CoordinatesOfTree{
static class Tree{
int data;
Tree left = null;
Tree right = null;
public Tree(int data){
this.data = data;
}
//create minimal bst
public static Tree createBST(int []a, int left, int right){
if(right < left)
return null;
int mid = (left + right)/2;
Tree root = new Tree(a[mid]);
root.left = createBST(a, left, mid - 1);
root.right = createBST(a, mid + 1, right);
return root;
}
}
static void printCoordinate(Tree root,int x, int y){
if(root == null)
return;
System.out.println(root.data +" : ("+x+","+y+")");
printCoordinate(root.left, x-1, y-1);
printCoordinate(root.right, x+1,y-1);
}
public static void main(String... args){
int[]arr = {1,2,3,4,5,6,7};
Tree root = Tree.createBST(arr, 0,arr.length-1);
printCoordinate(root,0, 0);
}
}
For example, let us consider the below tree:
Output: Coordinate of 4 : (0,0), Coordinate of 2 : (-1,-1), Coordinate of 3 : (1,-1), Coordinate of 1 : (-2,-2), Coordinate of 3 : (0,-2) etc.
Solution:
class CoordinatesOfTree{
static class Tree{
int data;
Tree left = null;
Tree right = null;
public Tree(int data){
this.data = data;
}
//create minimal bst
public static Tree createBST(int []a, int left, int right){
if(right < left)
return null;
int mid = (left + right)/2;
Tree root = new Tree(a[mid]);
root.left = createBST(a, left, mid - 1);
root.right = createBST(a, mid + 1, right);
return root;
}
}
static void printCoordinate(Tree root,int x, int y){
if(root == null)
return;
System.out.println(root.data +" : ("+x+","+y+")");
printCoordinate(root.left, x-1, y-1);
printCoordinate(root.right, x+1,y-1);
}
public static void main(String... args){
int[]arr = {1,2,3,4,5,6,7};
Tree root = Tree.createBST(arr, 0,arr.length-1);
printCoordinate(root,0, 0);
}
}
No comments:
Post a Comment