Please who can help with this question in Java

Thank you

Complete the following codes:

* An implementation of the BinaryTree interface by means of a linked structure. */

//import java.util.Iterator; import java.util.ArrayList; import java.util.Random;

public class LinkedBinaryTree implements BinaryTree { protected BTPosition root; // reference to the root protected int size; // number of nodes /** Creates an empty binary tree. */ public LinkedBinaryTree() { root = null; // start with an empty tree size = 0; } /** Returns the number of nodes in the tree. */ public int size() { return size; }

public boolean isEmpty() { return size() == 0;} /** Returns whether a node is internal. */ public boolean isInternal(Position v) throws InvalidPositionException { // your work is here }

public boolean isExternal(Position v) throws InvalidPositionException { // checkPosition(v); // auxiliary method return !isInternal(v); } /** Returns whether a node is the root. */ public boolean isRoot(Position v) throws InvalidPositionException { // your work is here. } /** Returns whether a node has a left child. */ public boolean hasLeft(Position v) throws InvalidPositionException { // Your work is here.

public boolean hasRight(Position v) throws InvalidPositionException { BTPosition vv = checkPosition(v); return (vv.getRight() != null); } /** Returns the root of the tree. */ public Position root() throws EmptyTreeException { if (root == null) throw new EmptyTreeException("The tree is empty"); return root; } /** Returns the left child of a node. */ public Position left(Position v) throws InvalidPositionException, BoundaryViolationException { // Your work is here. }

public Position right(Position v) throws InvalidPositionException, BoundaryViolationException { BTPosition vv = checkPosition(v); Position rightPos = vv.getRight(); if (rightPos == null) throw new BoundaryViolationException("No right child"); return rightPos; }

/** Returns the parent of a node. */ public Position parent(Position v) throws InvalidPositionException, BoundaryViolationException { BTPosition vv = checkPosition(v); Position parentPos = vv.getParent(); if (parentPos == null) throw new BoundaryViolationException("No parent"); return parentPos; } /** Returns an iterable collection of the children of a node. */ public Iterable> children(Position v) throws InvalidPositionException { ArrayList> children = new ArrayList>(); if (hasLeft(v)) children.add(left(v)); if (hasRight(v)) children.add(right(v)); return children; } /** Returns an iterable collection of the tree nodes. */ public Iterable> positions() { ArrayList> positions = new ArrayList>(); if(size != 0) inorderPositions(root(), positions); // assign positions in inorder return positions; } /** Returns an iterator of the elements stored at the nodes */ public Iterable iterator() { Iterable> positions = positions(); ArrayList elements = new ArrayList(); for (Position pos: positions) elements.add(pos.element()); return elements; // An iterator of elements } /** Replaces the element at a node. */ public E replace(Position v, E o) throws InvalidPositionException { BTPosition vv = checkPosition(v); E temp = v.element(); vv.setElement(o); return temp; } // Additional accessor method /** Return the sibling of a node */ public Position sibling(Position v) throws InvalidPositionException, BoundaryViolationException { BTPosition vv = checkPosition(v); BTPosition parentPos = vv.getParent(); if (parentPos != null) { BTPosition sibPos; BTPosition leftPos = parentPos.getLeft(); if (leftPos == vv) sibPos = parentPos.getRight(); else sibPos = parentPos.getLeft(); if (sibPos != null) return sibPos; } throw new BoundaryViolationException("No sibling"); } // Additional update methods /** Adds a root node to an empty tree */ public Position addRoot(E e) throws NonEmptyTreeException { if(!isEmpty()) throw new NonEmptyTreeException("Tree already has a root"); size = 1; root = createNode(e,null,null,null); return root; } /** Inserts a left child at a given node. */ public Position insertLeft(Position v, E e) throws InvalidPositionException { BTPosition vv = checkPosition(v); Position leftPos = vv.getLeft(); if (leftPos != null) throw new InvalidPositionException("Node already has a left child"); BTPosition ww = createNode(e, vv, null, null); vv.setLeft(ww); size++; return ww; }

/** Inserts a right child at a given node. */ public Position insertRight(Position v, E e) throws InvalidPositionException { BTPosition vv = checkPosition(v); Position rightPos = vv.getRight(); if (rightPos != null) throw new InvalidPositionException("Node already has a right child"); BTPosition ww = createNode(e, vv, null, null); vv.setRight(ww); size++; return ww; } /** Removes a node with zero or one child. */ public E remove(Position v) throws InvalidPositionException { BTPosition vv = checkPosition(v); BTPosition leftPos = vv.getLeft(); BTPosition rightPos = vv.getRight(); if (leftPos != null && rightPos != null) throw new InvalidPositionException("Cannot remove node with two children"); BTPosition ww; // the only child of v, if any if (leftPos != null) ww = leftPos; else if (rightPos != null) ww = rightPos; else // v is a leaf ww = null; if (vv == root) { // v is the root if (ww != null) ww.setParent(null); root = ww; } else { // v is not the root BTPosition uu = vv.getParent(); if (vv == uu.getLeft()) uu.setLeft(ww); else uu.setRight(ww); if(ww != null) ww.setParent(uu); } size--; return v.element(); }

/** Attaches two trees to be subtrees of an external node. */ public void attach(Position v, BinaryTree T1, BinaryTree T2) throws InvalidPositionException { BTPosition vv = checkPosition(v); if (isInternal(v)) throw new InvalidPositionException("Cannot attach from internal node");

if (!T1.isEmpty()) { BTPosition r1 = checkPosition(T1.root()); vv.setLeft(r1); r1.setParent(vv); // T1 should be invalidated } if (!T2.isEmpty()) { BTPosition r2 = checkPosition(T2.root()); vv.setRight(r2); r2.setParent(vv); // T2 should be invalidated } } /** If v is a good binary tree node, cast to BTPosition, else throw exception */ protected BTPosition checkPosition(Position v) throws InvalidPositionException { // Your work is here. } /** Creates a new binary tree node */ protected BTPosition createNode(E element, BTPosition parent, BTPosition left, BTPosition right) { return new BTNode(element,parent,left,right); }

/** Creates a list storing the the nodes in the subtree of a node, * ordered according to the ineorder traversal of the subtree. */ protected void inorderPositions(Position v, ArrayList> pos) throws InvalidPositionException {

// Your work is here. } public int depth (Tree T, Position v) { if (T.isRoot(v)) return 0; else return 1 + depth(T, T.parent(v)); } public int height1 (Tree T) { int h = 0; for (Position v : T.positions()) { if (T.isExternal(v)) h = Math.max(h, depth(T, v)); } return h; }

public int height2 (Tree T, Position v) { if (T.isExternal(v)) return 0; int h = 0; for (Position w : T.children(v)) h = Math.max(h, height2(T, w)); return 1 + h; }

public static void main(String[] args) { LinkedBinaryTree T = new LinkedBinaryTree(); Random rand = new Random(); int n = 100; int j; if (T.isEmpty()) T.addRoot(rand.nextInt(1000)); System.out.println("The root element is " + T.root().element()); Position p = T.root(); for (int i = 0; i <= n; i++) {

j = rand.nextInt(1000); if ( j % 2 == 0) { T.insertLeft(p, j); p = T.left(p); } else { T.insertRight(p, j); p = T.right(p); }

}

System.out.println("The size of tree is " + T.size()); System.out.println(); System.out.println("The height1 is " + T.height1(T)); System.out.println(); System.out.println("The height2 is " + T.height2(T, T.root())); System.out.println(); System.out.println("The depth of the root is " + T.depth(T, T.root())); System.out.println(); System.out.println("We print all elements in the tree"); int count = 0; for (Integer in: T.iterator()) {

System.out.print(in + " "); ++count; if(count % 10==0) System.out.println(); } System.out.println(); System.out.println();

} }