use java to write Find the Path To Root from a given tree node. Here, you will b
ID: 3918366 • Letter: U
Question
use java to write
Find the Path To Root from a given tree node.
Here, you will be creating a recursive method which is a specialized kind of find. You will be given an element in the tree to find, and once found, you will need to create an iterator which can traverse the elements along the path from the found element to the root of the tree. So, you will find the “path to root” for the node given as a parameter.
This method will be added to the LinkedBinaryTree.java file, and has the following header:
public Iterator pathToRoot(T targetElement) throws ElementNotFoundException{
Hint: You will need to create a recursive helper method, pathToRootAgain, as you did with the findAgain method.
Explanation / Answer
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
int[] arr = new int[100];
public boolean fn(Node root, Node required, int index){
if(null == root)return false;
arr[index] = root.data;
if(root.data == required.data){
printArray(arr, index+1);
return true;
}
if(fn(root.left, required, index+1) || fn(root.right, required, index+1)) return true;
return false;
}
void printArray(int ints[], int len)
{
int i;
for (i = 0; i < len; i++)
{
System.out.print(ints[i] + " ");
}
System.out.println("");
}
// driver program to test above functions
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(2);
tree.root.left.left.left=new Node(15);
tree.root.left.left.right=new Node(18);
int target=3;
/* Let us test the built tree by printing Insorder traversal */
tree.fn(tree.root, new Node(3), 0);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.