1. Printing the elements in a binary tree ordered by depth. The root has depth 0, the roots children have depth one, and so on.

For example, for the tree in the figure, your program should output:

Keys at depth 0: 10

Keys at depth 1: 4 15

Keys at depth 2: 2 8 12 18

Keys at depth 3: 1 3 5 9

Keys at depth 4: 7

bstNode.java

public class bstNode{ public int item; public bstNode left; public bstNode right; public bstNode(int i){ item = i; left = null; right = null; } public bstNode(int i, bstNode l, bstNode r){ item = i; left = l; right = r; } }

bst_ops.java

import java.util.Scanner; public class bst_ops{ public static bstNode insert(bstNode T, int i){ if (T==null) T = new bstNode(i); else if (ihr) return 1+hl; return 1+hr; } public static bstNode delete(bstNode T, int i){ if (T == null) return null; if (iT.item) T.right=delete(T.right,i); else // i == T.item if (T.left == null && T.right == null) T = null; else if (T.left == null && T.right != null) T = T.right; else if (T.left != null && T.right == null) T = T.left; else{ bstNode succ = min(T.right); T.item = succ.item; T.right = delete(T.right, succ.item); } return T; } public static void inOrder(bstNode T){ if (T!=null){ inOrder(T.left); System.out.print(T.item+" "); inOrder(T.right); } } public static void inOrderStack(bstNode T) { if(T == null) { return; } } public static void draw_tree(bstNode T, double x0, double x1, double y, double y_inc) { if(T ==null) return; double xm = (x0+x1)/2; double yn = y-y_inc; if(T.left!=null){ StdDraw.line(xm,y,(x0+xm)/2,yn); draw_tree(T.left,x0,xm,yn, y_inc); } if (T.right!=null){ StdDraw.line(xm,y,(x1+xm)/2,yn); draw_tree(T.right,xm,x1,yn, y_inc); } StdDraw.setPenColor(StdDraw.WHITE); StdDraw.filledCircle(xm,y, 3); StdDraw.setPenColor(StdDraw.BLACK); StdDraw.circle(xm,y, 3); StdDraw.text(xm,y,Integer.toString(T.item)); } public static void pause(){ Scanner s =new Scanner(System.in); System.out.println("Press enter to continue....."); s.nextLine(); StdDraw.clear(); } public static void main(String[] args) { int x_max =100; int y_max =100; StdDraw.setXscale(0, x_max); StdDraw.setYscale(0, y_max); StdDraw.setPenColor(StdDraw.BLACK); int [] A = {10, 16, 13, 17, 20, 19, 15, 4, 14, 8 ,9, 5, 2, 3, 7, 12, 18, 1, 6, 11};

bstNode B=null; for (int i=0;i

B = delete(B,18); pause(); draw_tree(B, 0, x_max, y_max-5, (y_max-10.0)/height(B)); B = delete(B,5); pause(); draw_tree(B, 0, x_max, y_max-5, (y_max-10.0)/height(B)); B = delete(B,10); pause(); draw_tree(B, 0, x_max, y_max-5, (y_max-10.0)/height(B));

} }