Question
In: Computer Science
3. Assume that binary trees are defined as public class BTNode<E> { private E data; private...
3. Assume that binary trees are defined as
public class BTNode<E>
{
private E data;
private BTNode<E> left, right;
}
We say that a binary tree t1 is a prefix of a binary tree t2 if t2 can be made identical to t1
by removing zero or more leaves of t2. Write a method
Solutions
Expert Solution
The best way i can think of for this problem is, comparing leaves of two trees and storing leaves beforehand
Now lets see an example, suppose, tree t1 has
A, b, c, d, e leaves in this order from left ro right, store them in a SET
Also, tree t2 has leaves
Now you just traverse the tree t2 and whenever you come across a leaf, you just check in same order as in t1 set,
Lets say, i is pinting on leaf b in t1
But while traversing, in t2 leaf j comes, but expected leaf was b, so you just make this leaf as null there itslef, you dont need it
The best part of algorithmi is its Time Complexity,
For finding leaves, it will take linear time O(N), nis number of nodes in tree
For traversing also linear time,
But can you guess what about comparing,
Its constant, O(1), as we are maintaining a pointer on t1 set, which increments after every successful comparison
Now i believe you got the algorithm, tell this to anyone, and he or she will be impressed.
As you learned how to think about a problem.
Note : writing code isnt, hard even GOOGLE nevet asks in interview to code necessarily, you need to have problem solving skills, and you learned a bit today.
I hope, this must have helped you.
Happy learning.
venereology answered 4 months agoRelated Solutions
Assume you have created the following data definition class: public class Book { private String title;...
Assume you have created the following data definition class:
public class Book {
private String title;
private double cost;
public String getTitle() { return this.title;
}
public double getCost() { return this.cost;
}
public void setTitle(String title) {
this.title = title;
}
// Mutator to return true/false instead of using exception
handling
public boolean setCost(double cost) {
if (cost >= 0 &&
cost < 100) {
this.cost =
cost;
return
true;
}
else {
return
false;
}...
Assume you have created the following data definition class: public abstract class Organization { private String...
Assume you have created the following data definition class:
public abstract class Organization {
private String name;
private int numEmployees;
public static final double TAX_RATE = 0.01;
public String getName() { return this.name; }
public int getNumEmployees() { return
this.numEmployees; }
public abstract double calculateTax() {
return this.numEmployees *
TAX_RATE;
}
}
In your own words, briefly (1-2 sentences) explain why the data
definition class will not compile. Then, write modified code that...
public class IntNode { private int data; pri
public class IntNode
{
private
int data;
private
IntNode link;
public
IntNode(int data, IntNode link){.. }
public
int getData(
) {.. }
public
IntNode getLink(
) {..
}
public
void setData(int data)
{.. }
public
void setLink(IntNode link) {.. }
}
All questions are based on the above class, and the following
declaration.
// Declare an empty, singly linked list with a head and a tail
reference.
// you need to make sure that head always points to...
public class StringNode { private String item; private StringNode next; } public class StringLL { private...
public class StringNode {
private String item;
private StringNode next;
}
public class StringLL {
private StringNode head;
private int size;
public StringLL(){
head = null;
size = 0;
}
public void add(String s){
add(size,s);
}
public boolean add(int index, String s){
...
}
public String remove(int index){
...
}
}
In the above code add(int index, String s) creates a StringNode
and adds it to the linked list at position index, and remove(int
index) removes the StringNode at position...
Task Generics: GenericStack Class. Java. package Modul02; public class GenericStack<E> { private java.util.ArrayList<E> list = new...
Task Generics: GenericStack Class. Java.
package Modul02;
public class GenericStack<E> {
private java.util.ArrayList<E> list = new
java.util.ArrayList<>();
public int size() {
return list.size();
}
public E peek() {
return list.get(size() - 1);
}
public void push(E o) {
list.add(o);
}
public E pop() {
E o = list.get(size() - 1);
list.remove(size() - 1);
return o;
}
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public String toString() {
return "stack: " + list.toString();
}
}
package Modul02;
public class TestGenericStack...
1. public class MyString { private char[] data; MyString(String string) { data = string.toCharArray(); } public...
1.
public class MyString {
private char[] data;
MyString(String string) { data = string.toCharArray(); }
public int compareTo(MyString other) { /* code from HW1 here */ }
public char charAt(int i) { return data[i]; }
public int length() { return data.length; }
public int indexOf(char c) { /* code from HW1 here */ }
public boolean equals(MyString other) { /* code from HW1 here */ }
/*
* Change this MyString by removing all occurrences of
* the argument character...
public class SinglyLikedList { private class Node{ public int item; public...
public class SinglyLikedList {
private class Node{
public int item;
public Node next;
public Node(int item, Node next)
{
this.item =
item;
this.next =
next;
}
}
private Node first;
public void addFirst(int a) {
first = new Node(a, first);
}
}
1. Write the method add(int item, int position), which takes an
item and a position, and...
Data structure Give three distinct binary search trees for the following data: 1 2 3 4...
Data structure
Give three distinct binary search trees for the
following data: 1 2 3 4 5 6 7. One of these trees must
have minimum height and another must-have maximum height.
Draw the BSTs that result from each sequence of add operations.
(2) a. 10, 20, 30, 40 b. 30, 20, 40, 10 c. 20, 10, 30, 40
Data structure Give three distinct binary search trees for the following data: 1 2 3 4...
Data structure
Give three distinct binary search trees for the
following data: 1 2 3 4 5 6 7. One of these trees must
have minimum height and another must-have maximum height.
Draw the BSTs that result from each sequence of add operations.
(2) a. 10, 20, 30, 40 b. 30, 20, 40, 10 c. 20, 10, 30, 40
Question 1: Processing Compound Data: Binary Trees A binary tree is a tuple with the following...
Question 1:
Processing Compound Data: Binary Trees
A binary tree is a tuple with the following recursive
structure
("btree", [val, left_tree, right_tree])
where first part of the tuple is a string "btree" and
second part of the tuple is a list in which val is the value at the
root and left_tree and right_tree are the binary trees for the left
and right children or
("btree",[]) for the empty
tree.
(A)
Implement a binary tree ADT.
Type Name Description
Create...
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- How many grams of Na2CO3 should be mixed with 5.00 g of NaHCO3 to produce 100...
- Given the following information for a monopolistic competitor: Demand: P = 78 – 5(Q) Marginal revenue:...
- Why does the auto industry prefer uniform (national) standards for automobile emissions as opposed to regionally...
- GOAL Apply the more general definition of torque. PROBLEM (a) A man applies a force of...
- a) If 8.00 hp are required to drive a 1800-kg automobile at 54.0 km/h on a...
- 23- Celsius Corp. is conducting a capital budgeting analysis to decide whether to invest in a...
- Using energy level diagrams, predict the relative stability of a Br2 molecule as well as the...
ADVERTISEMENT