Remove Node from Binary Search Tree
I am working on Binary Search Tree for the first time and trying to remove a node from the Binary Search Tree.
However, everytime I remove it and then I use inOrder()
or preOrder()
to check if it's removed or not, it still shows up, which means I fail to remove that particular node.
This is my code:
public class BinaryTree<T extends Comparable<T>> {
TreeNode<T> root;
ArrayList<Integer> myArr = new ArrayList<Integer>();
Random random;
}
public void add(T o) {
if (root == null) {
root = new TreeNode<T>(o);
} else {
root.insert(o);
}
}
public TreeNode<T> deleteNode(TreeNode<T> root, int value) {
if (root == null)
return null;
if (root.data > value) {
root.left = deleteNode(root.left, value);
} else if (root.data < value) {
root.right = deleteNode(root.right, value);
} else {
// if nodeToBeDeleted have both children
if (root.left != null && root.right != null) {
TreeNode<T> temp = root;
// Finding minimum element from right
TreeNode<T> minNodeForRight = minimumElement(temp.right);
// Replacing current node with minimum node from right subtree
root.data = minNodeForRight.data;
// Deleting minimum node from right now
deleteNode(root.right, minNodeForRight.data);
}
// if nodeToBeDeleted has only left child
else if (root.left != null) {
root = root.left;
}
// if nodeToBeDeleted has only right child
else if (root.right != null) {
root = root.right;
}
// if nodeToBeDeleted do not have child (Leaf node)
else
root = null;
}
return root;
}
public TreeNode<T> minimumElement(TreeNode<T> root) {
if (root.left == null){
return root;
} else {
return minimumElement(root.left);
}
}
public static void main(String[] args){
BinaryTree<Integer> bst = new BinaryTree<Integer>();
bst.add(20);
bst.add(30);
bst.add(40);
bst.add(80);
bst.add(1200);
bst.inOrder();
bst.deleteNode(bst.root, 80);
bst.inOrder();
}
How to solve this problem?
1 answer

Change following line
// Deleting minimum node from right now deleteNode(root.right, minNodeForRight.data);
To
// Deleting minimum node from right now root.right = deleteNode(root.right, minNodeForRight.data);
See also questions close to this topic

Export Project from Netbeans as 32 bit Installer
I want to export my Java Swing project as .exe Installer for 32 bit platform.
I've OS : Windows 10, 64 bit Netbeans Version : 8.2
What should I do?
Also I want to know whether I can make .exe Installer with embedded Oracle Database.

Incorrect parsing response from feign client
I have a simple
Feign client
:@FeignClient( serviceId = "${com.service}", fallbackFactory = AccountFeignServiceClient.AccountFallBackFactory.class) public interface AccountFeignServiceClient { @GetMapping("/users/{id}") ResponseEntity<AccountDto> getUser(@PathVariable("id") String id); }
Method in another server:
@GetMapping(value = "/users/{id}") ResponseEntity<?> getUser(@PathVariable(value = "id") String id) { return ok(...); }
Problem is that
AccountDto
have onlynull
fields. Afterdebag
I found the following reason for this behavior. If i get the response in infeign client
of typestring
it will be like:{"headers":{},"body":{"id":"d267294fd4b2493b982963ece48922e9"},"statusCode":"OK","statusCodeValue":200}
But if i get the response of type
ResponseEntity<?>
i will get this:You can see it have double
body
and i have no ideas why. With typeResponseEntity<?>
i expect response like: 
Find an object in Hibernate without id
I'm using Spring. I have a user table.
When a person logins to the system, he sends me his credentials (i.e. username and password).
I stored my users in database with "incremental generated uid" (i.e. userid is primary key).
I also stored the username password etc. in the database. What I need to do is, when the user connects to the Rest connection, I need to check whether the database has this user or not. If he exists, then I need to check if passwords are matching. And I need to do that checking by username, rather than uid
I dont have session or anything at all in my program (Or as far as I know, I didn't write any session or sessionfactory in my code at all)
My repository class:
public interface UserRepository extends JpaRepository<User, Long>{ }
My user DAO
@Service public class UserDAO { @Autowired UserRepository userRepository; public User findByUsername(String username) { //what to write here } }
I've looked up this solution but as I stated above, I don't have session.

Are there any efficient ways to populate a balanced tree structure
I have a balanced binary tree structure:
Node
0
at depth0
is the root. The root's left child is1
and right child is2
, and so on.The total depth of the tree is given as
N
. ThisN
is the only parameter of the problem. Nodes at levelN
are designated as leaf nodes.I am storing this tree using the following node structure.
struct node_s{ int n, depth, parent;//n is node number int nodescendents;//number of descendents of the current node std::vector<int> descendents;//Descendents in ascending order int lchild, rchild;//Immediate left child and right child std::vector<int> lchildleaves;//leaf nodes that descend from the immediate //left child std::vector<int> rchildleaves;//leaf nodes that descend from the immediate //right child };
I intend to store the tree itself as:
std::vector<node_s> tree;
Is there a way to numerically efficiently populate the
tree
vector using simple algebra roughly as://Creating the nth node, beginning from 0th node, then 1st node and so on nodes_s node; //populate all data structures of the nth node //precisely, here, there are loops, algebraic calculations, etc., that can help //populate all of the node_s data members. tree.push_back(node);
The only way I can think of as of now is to construct a graph explicitly and run some sort of Dijkstra algorithm to figure out these data structure values for each node.

Decision Tree How to insert items to the right or left of node?
Say I have a List of Numbers I want to insert everything in the A1 column to the left if it's bigger than A1, if it's not bigger than I want to insert it to the right of my decision node. Something like this diagram.
To manage the data I created a struct and each line would be a data object of its own so the first line (1,4) is one data and (77,6) is another.
I'm not sure how to organize that data where values in the A1 column that A1 > 8 is on the left else on the right.
How would I store the values of my vector in to one node, and map the correct classification to the values for instance right of A1 > 8 would have values (8, 1) and their respective classification is (yes, yes)
struct data { string group; vector<double> values; };

weka desicion tree has empty conjuctions
Here is the Tree, near the top of the tree by the root, the branched off conjuctions are empty which I don't understand.
The TextDirectoryLoader, StringToWordVector filter, AttributeSelection filter, and J48 decision tree classification operations were applied to the data as well as Lovins Stemmer.
The data has to do with identifying fake news articles by text files.
What are these empty conjutions? I can't find anything similar.

How can i Find biggest binary number before a number in c++?
I want to find biggest binary number before a number Like Biggest binary number before 3567 is 1111 In c++

Java numeric conversion is unclear
Consider the following piece of code:
byte newBytes[] = new byte[(myBytes.length + 8) & ~7];
I understand java doesn't really deal with unsigned ints, so if the length of myBytes was INT_MAX, then adding to the length would overflow into a negative number.
But, what is the
~7
doing?If:
myBytes = 2147483647
, then2147483647 + 8 = 2,147,483,641
ANDing
~7
to that, just makes it2,147,483,648
.. still a negative number.Is this just wonky code or is there a java subtlety that a clever programmer is exploiting here?

Serve xlsx file from MongoDB binary using Node.js
I have some Excel documents (xlsx) saved in MongoDB in binary. I would like node.js to retrieve a file from the database when a user navigates to a url and serve the file for the user to download. I'm successfully downloading a file, but I'm getting an error from Excel when trying to open the file:
"Excel cannot open the file '5beec8ef3cf3e70b5ce8972e.xlsx' because the file format or file extension is not valid. Verify that the file has not been corrupted and that the file extension matches the format of the file."
The file is also saving with 0 bytes. I think I am not correctly converting the data from MongoDB before trying to create the buffer. Here's my script:
app.get('//downloadReport/:id', (req, res) => { dbo = db.db('test'); dbo.collection("reports").findOne( {'_id': mongodb.ObjectId(req.params.id)} ).then(doc => { console.log('type of doc.file: ' + typeof doc.file); // returns: // type of doc.file: object console.log(doc.file); // returns: // Binary { // _bsontype: 'Binary', // sub_type: 0, // position: 1146504, // buffer: <Buffer 50 4b 03 04 14 00 00 00 08 00 12 66 6f 4d f8 64 19 ... > } res.writeHead(200, [['ContentType', 'application/vnd.openxmlformatsofficedocument.spreadsheetml.sheet']]); // This one doesn't work // res.end(doc.file, 'binary'); // returns: // TypeError: First argument must be a string or Buffer res.end(new Buffer(doc.file, 'binary') ); }); });
I've tried drilling down to
doc.file.Binary.buffer
, but I get an error sayingdoc.file.Binary
is not defined.I also want the file to download with the correct file name. I've tried adding this to
writeHead
:['Contentdisposition', 'filename=' + doc.filename]
but I get an error in Chrome:
ERR_RESPONSE_HEADERS_MULTIPLE_CONTENT_DISPOSITION
Anyone know how to make this work? Thanks in advance!

Absolutely fried on implementing rotation in a C++ binary search tree
I've spent several hours trying to make this darn thing work, and at this point my brain is so fried I can barely explain what I'm trying to do. I'll admit it's homework, but I'm 100% lost on how to make progress, and it's one of the very few things I have left in this project. The rotation functions are taken (with permission) from lecture notes, but by god I can't get them to work.
contains() is supposed to check whether an element exists somewhere in the tree, and if that element has been searched for
search_threshold
times, rotate it one position higher in the tree.I tried my own messy solution for a while, but it didn't work nearly the way it needed to. For now I was just shooting to get a really basic case for rotation working, where the node that's being moved up has no children, but even that seems to be dropping nodes. Any tips how to get back on track?
//BSTNode is a struct with T element, BSTNode *left = NULL, BSTNode *right = NULL, BSTNode *parent = NULL, int search_count = 0
Abbreviated code as follows:
template <typename T> void BST< T >::rotateWithLeftChild(BSTNode *& k2) { BSTNode *k1 = k2>left; k2>left = k1>right; k1>right = k2; k2 = k1; } template <typename T> void BST< T >::rotateWithRightChild( BSTNode *& k2) { BSTNode *k1 = k2>right; k2>right = k1>left; k1>left = k2; k2 = k1; } template <typename T> void BST< T >::doubleWithRightChild( BSTNode *& k3 ) { rotateWithLeftChild( k3>right ); rotateWithRightChild( k3 ); } template <typename T> void BST< T >::doubleWithLeftChild( BSTNode *& k3 ) { rotateWithRightChild( k3>left ); rotateWithLeftChild( k3 ); } template <typename T> bool BST< T >::contains(const T& v, BSTNode *&t) { // If the node doesn't exist, return false if (t == NULL) return false; // If the node exists, return true if (t>element == v) { // Increment search count t>search_count++; // If search count is above threshold, if (t>search_count >= threshold) { cout << "Search count above threshold" << endl; // Reset search count t>search_count = 0; if (t == root) return true; // Faaaaaairly confident that my bug is here if (t>left != NULL && t>right != NULL) { cout << "parent element: " << t>parent>element << endl; if (t == t>parent>left) rotateWithLeftChild(t>parent); } } return true; } // Otherwise, return the OR of the children's contains() else return (contains(v, t>left)  contains(v,t>right)); }

Comparing BST node with str issue
This is the search function I'm using to try and find a specific value held in a BST that holds words. However when I run it I am given an error on the line
elif root < root.value:
def search(root, target): print("Target is: " + target + "\n") if root.value == target or root == None: print("Found target: " + target) return root elif root < root.value: return search(root.left, target) print("Searching left") else: return search(root.right, target) print("Searching right")
It says
TypeError: '<' not supported between instances of 'Node' and 'str'
, now as far as I know I can use<
and>
too compare regular strings, but I cant seem to use it to compare a root a node containing a string and another node containing a string? Is their another way I should go about comparing? 
Which node do I check in an AVL Tree to decide whether I need to rotate the tree? Sample code in C++
I'm trying to understand why this code works.
It seems to me that there's a mistake in the function insert.
Since prev will be the parent node of the new node we're going to insert into the tree, I don't see how the difference in the heights of the left and right children of the parent can be more than one, and so I don't see why rotation would ever occur.
After insertion, prev will either have a left and a right child, or just one child.
If the parent has one child then the difference in heights is 1.
If the parent has two children then the difference in heights is 0.
Can someone tell me what I'm missing here?
#include <iostream> #include <ctime> using namespace std; template <class T> class AVL; template <class T> T& max(T& left, T& right){ if (left > right) return left; else return right; } template <class T> T max(const T& left, const T& right){ if (left > right) return left; else return right; } /* $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ */ template <class T> class AVLNode{ AVLNode<T>* parent, *left, *right; int height; T data; public: friend class AVL < T >; AVLNode(const T& newdata = T(), AVLNode<T>* newparent = nullptr, AVLNode<T>* newleft = nullptr, AVLNode<T>* newright = nullptr) : data(newdata), parent(newparent), left(newleft), right(newright) { calcHeight(); } void calcHeight(){ int leftHeight = 1; int rightHeight = 1; if (left != nullptr) leftHeight = left>height + 1; if (right != nullptr) rightHeight = right>height + 1; height = max(leftHeight, rightHeight) + 1; } void printInOrder()const{ if (left != nullptr) left>printInOrder(); cout << data << endl; if (right != nullptr) right>printInOrder(); } int size()const{ int leftSize = 0; int rightSize = 0; if (left != nullptr) leftSize = left>size(); if (right != nullptr) rightSize = right>size(); return 1 + leftSize + rightSize; } /* int height()const{ int leftSize = 1; int rightSize = 1; if (left != nullptr) leftSize = left>height(); if (right != nullptr) rightSize = right>height(); return 1 + max(leftSize, rightSize); }*/ int depth() const{ int parentDepth = 1; if (parent != nullptr) parentDepth = parent>depth(); return 1 + parentDepth; } }; /* $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ */ template <class T> class AVL{ AVLNode<T>* root; int size; AVLNode<T>* recursiveCopy(AVLNode<T>* toCopy); void singleCCR(AVLNode<T>*& point); void doubleCR(AVLNode<T>*& point); void singleCR(AVLNode<T>*& point); void doubleCCR(AVLNode<T>*& point); int heightDiff(AVLNode<T>* point); void doRotation(AVLNode<T>* point); public: AVL() :size(0){ root = nullptr; } //memory on the heap so.... here comes the big 3! AVL(const AVL<T>& rhs) :root(nullptr){ *this = rhs; } virtual ~AVL(){ clear(); } AVL& operator=(const AVL<T>& rhs); bool isInTree(const T& toFind) const{ return find(toFind) != nullptr; } bool isEmpty()const{ return root == nullptr; } int getSize()const { return size; } void remove(const T& toRemove){ AVLNode<T>* item = find(toRemove); if (item != nullptr) remove(item); } void insert(const T&); void remove(AVLNode<T>*); AVLNode<T>* find(const T& toFind) const; void clear(){ while (!isEmpty()) remove(root); } void printInOrder()const{ root>printInOrder(); } }; template <class T> void AVL<T>::doubleCCR(AVLNode<T>*& point){ singleCR(point>right); singleCCR(point); } template <class T> void AVL<T>::doubleCR(AVLNode<T>*& point){ singleCCR(point>left); singleCR(point); } template <class T> void AVL<T>::singleCR(AVLNode<T>*& point){ AVLNode<T>* grandparent = point; AVLNode<T>* parent = point>left; parent>parent = grandparent>parent; grandparent>parent = parent; grandparent>left = parent>right; parent>right = grandparent; if (grandparent>left != nullptr) //if we now have a left child, update its parent pointer grandparent>left>parent = grandparent; if (parent>parent == nullptr)//if we were the root, update the root! root = parent; else if (parent>parent>left == grandparent) parent>parent>left = parent; else parent>parent>right = parent; grandparent>calcHeight(); parent>calcHeight(); } template <class T> void AVL<T>::singleCCR(AVLNode<T>*& point){ AVLNode<T>* grandparent = point; AVLNode<T>* parent = point>right; parent>parent = grandparent>parent; grandparent>parent = parent; grandparent>right = parent>left; parent>left = grandparent; if (grandparent>right != nullptr) //if we now have a right child, update its parent pointer grandparent>right>parent = grandparent; if (parent>parent == nullptr)//if we were the root, update the root! root = parent; else if (parent>parent>right == grandparent) parent>parent>right = parent; else parent>parent>left = parent; grandparent>calcHeight(); parent>calcHeight(); } template <class T> AVLNode<T>* AVL<T>::recursiveCopy(AVLNode<T>* toCopy){ if (toCopy == nullptr) return nullptr; AVLNode<T>* temp = new AVLNode<T>(toCopy>data, nullptr, recursiveCopy(toCopy>left), recursiveCopy(toCopy>right)); if (temp>left != nullptr) temp>left>parent = temp; if (temp>right != nullptr) temp>right>parent = temp; return temp; } template <class T> AVL<T>& AVL<T>::operator=(const AVL<T>& rhs){ if (this == &rhs) return *this; clear(); root = recursiveCopy(rhs.root); size = rhs.size; return *this; } template <class T> void AVL<T>::remove(AVLNode<T>* toRemove){ if (root == nullptr) return; //Remove from an empty tree???? if (toRemove>left == nullptr && toRemove>right == nullptr){ //leaf node case if (toRemove>parent == nullptr){ root = nullptr; } else if (toRemove == toRemove>parent>left) //left child! toRemove>parent>left = nullptr; //fix the parent's pointer! else toRemove>parent>right = nullptr; delete toRemove; size; } else if (toRemove>right == nullptr){ //has one (left) child if (toRemove>parent == nullptr){ root = toRemove>left; root>parent = nullptr; } else if (toRemove == toRemove>parent>left){ //we're the left child of our parent toRemove>parent>left = toRemove>left; toRemove>left>parent = toRemove>parent; } else{ toRemove>parent>right = toRemove>left; toRemove>left>parent = toRemove>parent; } delete toRemove; size; } else if (toRemove>left == nullptr){ //has one right child, almost same solution as left child only if (toRemove>parent == nullptr){ root = toRemove>right; root>parent = nullptr; } else if (toRemove == toRemove>parent>left){ //we're the left child of our parent toRemove>parent>left = toRemove>right; toRemove>right>parent = toRemove>parent; } else{ toRemove>parent>right = toRemove>right; toRemove>right>parent = toRemove>parent; } delete toRemove; size; } else{ //sigh... two children! AVLNode<T>* temp = toRemove>right; while (temp>left != nullptr) temp = temp>left; toRemove>data = temp>data; remove(temp); } } template <class T> AVLNode<T>* AVL<T>::find(const T& toFind) const{ AVLNode<T>* temp = root; while (temp != nullptr && temp>data != toFind){ if (toFind < temp>data) temp = temp>left; else temp = temp>right; } return temp; } template <class T> void AVL<T>::insert(const T& toInsert){ size++; if (root == nullptr){ root = new AVLNode<T>(toInsert); } else{ // if prev isn't root then shouldn't we look at prev's parent for heightDiff and rotation? AVLNode<T>* temp = root; AVLNode<T>* prev = temp; while (temp != nullptr){ prev = temp; if (toInsert < temp>data) temp = temp>left; else temp = temp>right; } //now temp points to null and prev points to the node we want to insert onto if (toInsert < prev>data){ //insert onto the left of Prev prev>left = new AVLNode<T>(toInsert, prev); } else prev>right = new AVLNode<T>(toInsert, prev); if(prev != nullptr){ // when would prev be nullptr? prev>calcHeight(); if (heightDiff(prev)>1) // wouldn't only prev's parent have the possibility of > 1? **** doRotation(prev); // how could it ever be larger than 1? } } } template <class T> void AVL<T>::doRotation(AVLNode<T>* point){ int leftChild = 1; int rightChild = 1; if (point>left != nullptr) leftChild = point>left>height; if (point>right != nullptr) rightChild = point>right>height; if (leftChild > rightChild){//CR, but is it single or double? int leftGC = 1; int rightGC = 1; if (point>left>left != nullptr) leftGC = point>left>left>height; if (point>left>right != nullptr) rightGC = point>left>right>height; if (leftGC > rightGC) // single rotation singleCR(point); else doubleCR(point); } else{//definitely a CCR, but which one? int leftGC = 1; int rightGC = 1; if (point>right>left != nullptr) leftGC = point>right>left>height; if (point>right>right != nullptr) rightGC = point>right>right>height; if (leftGC > rightGC) // double rotation doubleCCR(point); else singleCR(point); } } template<class T> int AVL<T>::heightDiff(AVLNode<T>* point){ int leftHeight = 1; int rightHeight = 1; if (point>left != nullptr) leftHeight = point>left>height; if (point>right != nullptr) rightHeight = point>right>height; return (abs(leftHeight  rightHeight)); } /* $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ */ int main(){ { AVL<int> b; srand(time(NULL)); for (int i = 0; i < 100; i++) b.insert(rand() % 1000); b.printInOrder(); cout << "Got here!" << endl; } cout << "Got here #2" << endl; }