HAS TO BE DONE IN RUST!! Implement a [binary search tree](https://en.wikipedia.o
ID: 3571515 • Letter: H
Question
HAS TO BE DONE IN RUST!! Implement a [binary search tree](https://en.wikipedia.org/wiki/Binary_search_tree) that supports insert, search, and [traversal](https://en.wikipedia.org/wiki/Tree_traversal). ## Public API Your program must provide the following public API. ``` pub struct Tree<T> { ... } impl<T: Ord> Tree<T> { /// Creates an empty tree pub fn new() -> Self { unimplemented!() } /// Returns `false` if `key` already exists in the tree, and `true` otherwise. pub fn insert(&mut self, key: T) -> bool { unimplemented!() } /// Returns `true` if `key` exists in the tree, and `false` otherwise. pub fn find(&self, key: &T) -> bool { unimplemented!() } /// Returns the preorder traversal of the tree. pub fn preorder(&self) -> Vec<&T> { unimplemented!() } /// Returns the inorder traversal of the tree. pub fn inorder(&self) -> Vec<&T> { unimplemented!() } /// Returns the postorder traversal of the tree. pub fn postorder(&self) -> Vec<&T> { unimplemented!() } } ```
Explanation / Answer
public class BinaryTree
{
private Node root;
public BinaryTree()
{
root=null;
}
public boolean insert(int value)
{
Node temp=new Node(value);
if(root==null)
{
root=temp;
return true;
}
else
{
Node temp=root;
Node parent=null;
while(true)
{
parent=temp;
if(temp.getValue()>value)
{
temp=temp.getLeft();
if(temp==null)
{
parent.setLeft(temp);
return true;
}
}
else
{
temp=temp.getRight();
if(temp==null)
{
parent.setRight(temp);
return true;
}
}
}
}
}
public boolean find(int value)
{
if(root==null)
System.out.println("tree is empty");
else
{
Node temp=root;
while(true)
{
if(temp.getVlaue()==value)
return true;
if(value<temp.getValue())
temp=temp.getLeft();
else
temp=temp.getRight();
if(temp==null)
return false;
}
}
return false;
}
public void preorder(Node root)
{
if(root!=null)
{
System.out.println(" "+root.getValue());
preorder(root.getLeft());
preorder(root.getRight());
}
}
public void displaypre()
{
preorder(root);
System.out.println(" ");
}
public void inorder(Node root)
{
if(root!=null)
{
inorder(root.getLeft());
System.out.println(" "+root.getValue());
inorder(root.getRight());
}
}
public void displayin()
{
inorder(root);
System.out.println(" ");
}
public void postorder(Node root)
{
if(root!=null)
{
postorder(root.getLeft());
postorder(root.getRight());
System.out.println(" "+root.getValue());
}
}
public void displaypost()
{
postorder(root);
System.out.println(" ");
}
}
public class Tree
{
public static void main(String[] args)
{
BinaryTree b=new BinaryTree();
b.insert(9);
b.insert(25);
b.insert(11);
b.insert(3);
b.insert(10);
b.insert(235);
b.insert(517);
b.insert(143);
System.out.println("Inorder traversal is");
b.displayin();
System.out.println("Preorder traversal is");
b.displaypre();
System.out.println("Postorder traversal is");
b.displaypost();
System.out.println(b.find(11));
System.out.println(b.find(25));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.