The (full-l full-r) case is all messed up. To handle that case, you need to pick either what Wikipedia calls the "in-order predecessor" or the "in-order successor" of the instance of bst being handled by replace, then delete that key from replace's bst and make it be the replacement. These...

c++,algorithm,tree,binary-search-tree,median

Make index a static local variable in the function findMedian. This is not recommended but one solution when it is insisted on having one const recursive function.

java,algorithm,reference,binary-search-tree

You have to delete the node from the tree and not locally in your program. Node<Integer> nodeToBeDeleted = getNode(deletionNodeValue); gives you a copy of the Node in the tree. nodeToBeDeleted = null; sets this copy to null. The connection to the tree is not deleted because it is part of...

If you do an in-order traversal of a reversed BST you will get the numbers sorted in descending order. So in that case the order for your values will be: 20, 15, 10, 8, 6, 4, 2. So the successor of 8 will be 6.

java,binary-search-tree,treenode

void updateDepth(Node node, int depth) { if (node != null) { node.depth = depth; updateDepth(node.left, depth + 1); // left sub-tree updateDepth(node.right, depth + 1); // right sub-tree } } Call with updateDepth(root, 0);...

c,tree,binary-search-tree,tree-traversal

The tree structure you are ending up is something like below 10 \ 20 / 15 The order of traversal will be as below: In-order: 10 15 20 Pre-order: 10 20 15 Post-order: 15 20 10 BST does maintain the property that elements in the lef-subtree are smaller than the...

data-structures,hashtable,binary-search-tree

The full text of that section states, with the last paragraph being the one you asked about: A hash table is a data structure that maps keys to values for highly efficient lookup. In a very simple implementation of a hash table, the hash table has an underlying array and...

java,binary-search-tree,treenode

Accessing right/left in that way would imply a TreeNode that is implemented in this way: public class TreeNode<T> { public TreeNode<T> right; public TreeNode<T> left; public T value; } ...

time,big-o,time-complexity,binary-search-tree,binary-search

Update Yes, You are absolutely right. In the worst case function() will be invoked 31 times, and each invocation requires time O(n), hence the running time of your algorithm is simply given by 31 * O(n) = O(n). Solution for the original question where x = function(mid) Your question is...

algorithm,data-structures,tree,binary-search-tree

In the general case, your algorithm needs perform a series of tree manipulations in the form of sub-tree rotation (as described in @Quicky's answer). The algorithm should look like this: While node_to_be_root is not the root of the whole tree: Rotate the sub-tree where the node_to_be_root is the pivot and...

java,binary-search-tree,anonymous-inner-class

Since sum is of type Traverser, you can only call on methods declared in the Traverser interface. Your options are: Just add the function public int totalTime(); to the interface definition. Create a 2nd interface with the desired function declaration that extends Traverser. Create an inner class that is not...

java,recursion,binary-search-tree

The compareTo method lets you compare any object that implements the Comparable interface. Since the String class implements the Comparable interface, compareTo will work in your method. A handy trick to remember when using compareTo is thinking of it like subtraction: a.compareTo(b) will return -1 if a - b results...

c++,c,pointers,segmentation-fault,binary-search-tree

Since searchSpecific may return NULL, you need to protect your code from it, and check x before accessing one of its members: tree *x=searchSpecific(root,f); if (x != NULL && x->left) ...

When you delete a node, you need change the according child field of its parent. But in your code, you only pass in the node-to-delete itself (node_t *root) so the parent node is left unchanged. In the single child case, you work around it by copying the single child to...

The height of every unbalanced BST is not O(lg n) because imagine a tree with keys in increasing/decreasing order, where the tree becomes skewed to one side. This happens to be the O(n) worst-case for an unbalanced BST where the height is equal to n. On the other hand, with...

java,algorithm,binary,binary-tree,binary-search-tree

Don't overthink it. It's simply because of the remove operation which always goes to the far left element and removes it. After several of these operations, you would end up with the tree being "heavier" to the right of the tree, regardless of root node or anything else. Even if...

java,algorithm,data-structures,graph,binary-search-tree

Try this code: public AlbumNode getAlbum(AlbumNode node, String name) { if (node == null) { // this checks the base case return null; // your original code failed for a null root } else { if (node.getName().equals(name)) { return node; } else { AlbumNode result = getAlbum(node.left, name); if (result...

data-structures,tree,heap,binary-search-tree,avl-tree

A heap may have better insert and merge times. It really depends on the type of heap, but typically they are far less strict than an AVL because they don't have to worry about auto balancing after each operation. A heap merely guarantees that all nodes follow the same style...

haskell,functional-programming,binary-search-tree

foldr recieve 3 arguments. A binary function (operator), the accumulator (neutral operand of the operator) and the structure (List). And you call function could be: foldr (&&) true $ map (member mBST) myList :t member mBST member mBST :: (Ord a) => a -> Bool map function aplied an unary...

java,binary-search-tree,equals

I cannot just add the values of the node to check if the trees are equal. Sure you can. hashCodes do not have to be unique, and if two BSTs have the same contents, then summing the node contents will give you the same results in each case, which...

c,binary-tree,binary-search-tree

First I think you should change strcmp(node->string,char s); And replace it with strcmp(node->string,s); In strcmp if the result is greater than zero then the first argument is greater than the second. So if your if else statement evaluates true then node->string is greater than s. And if strcmp is less...

In your insertNode method, you do not allocate any space for your node and you use an uninitialized pointer: TreeNode<T> *newNode; newNode->value = val; newNode->left = newNode->right = NULL; You need to allocate some memory for your node: TreeNode<T> *newNode = new TreeNode<T>; I highly recommend learning to use the...

The issue is a misunderstanding of Java referencing as seen with this section of code. private void insertPrivate(Node node, int x) { if(node == null) { node = new Node(x); } .... Java references are passed by value into function arguments. Let me give you an example to clarify. Node...

c++,data-structures,tree,binary-tree,binary-search-tree

The main work is being done in getMaxWidthRecur. It's initially given the parameter level = 0. The level parameter is incremented by 1 whenever we recurse down one level in the tree. The recursion will hit each node in the tree exactly once, and for each node in the tree,...

java,binary-search-tree,frequency

There are two issues in your code. This performs a pointer comparison: if ( w == n.getData() ). You want to compare the data inside the objects, so instead write if ( w.equals(n.getData()) ). But now you still need to override Word.equals() so that it returns true whenever the two...

java,recursion,binary-search-tree

Your problem is that when you return from one level in the recursive stack indicating that you found the target, you forget to use this information at the higher levels to stop the search. Try this (remove the print statements in your final product of course): private static boolean modifiedInorderTraversal(Node...

c++,recursion,binary-search-tree,deleting

remove_helper is attempting to change the value of the inRoot parameter. However inRoot is passed by value, so any changes made in your function are not reflected in the calling function. Change the remove_helper function to take inRoot by reference, and then it will be able to modify the value...

When you call a method, and use variables as arguments, the variables are not passed into the method - only their values. That is why this: class Test1 { static void addOne(int i) { i++; } public static void main(String[] args) { int x = 5; addOne(x); System.out.println(x); } }...

See operator precedence, where -> is having precedence over *. You should use (*root)->name as argument to your strncmp() call.

python,binary-search-tree,depth

Your recursive function depth needs a break condition: def depth(tree): if tree == None: return 0 else: return 1 + max(depth(tree.getLeftChild()), depth(tree.getRightChild())) And you forgot a max around the depths of the subtrees. Your snippet above fails as soon as tree == None (when a node has no child on...

Your code has a few errors to mention You are always reassiging head in the InsertAtHead() function. You should instead keep a reference to the tail of the list, and update the next node on each call to InsertAtHead(). You are passing an integer to ReversePrint() which is expecting a...

haskell,types,binary-search-tree,membership

Node isn't a type; it's a: value of type BinaryTree when fully applied a data constructor for such a value (a -> BinaryTree a -> BinaryTree a -> BinaryTree a) Both really mean the same, but it can be helpful to realize the appearance in two different contexts, namely pattern...

It appears that 45 does not have a left node, it is NULL, so checking pRoot->pleft->value == value is undefined behavior. 30 / \ 15 45 / \ \ 7 17 69 \ 80 So you need to do a check, something like: Node* BST::searchforparentnode(Node* pRoot, int value) { if(pRoot->pleft...

c,algorithm,pointers,binary-search-tree

The primary problem is not the way you're passing n; the primary problem is that *n-- decrements the pointer, not the pointed at value. You need (*n)-- to decrement the value pointed at. With that fixed, your code is most of the way there — despite my red herring comments...

functional-programming,scheme,binary-search-tree

Can you generalize the BST parameter like this? (define (insertB L BST) (if (not (null? L)) (insertB (cdr L) (insert (car L) BST)) BST ) ) Or the equivalent: (define (insertB L BST) (if (null? L) BST (insertB (cdr L) (insert (car L) BST)) ) ) I think it's easier...

java,recursion,nodes,binary-search-tree

if (root == null) { BSTNode<T> node = new BSTNode<>(data); root = node; } else { addRec(root, data); } size++; In this code, you increment size whether or not a duplicate element was found or whether or not the tree was actually changed. Therefore the unit test is (correctly) identifying...

java,binary-search-tree,breadth-first-search

Your traversal function is correct. You may want to check this online tool https://www.cs.usfca.edu/~galles/visualization/BST.html It provides visualization of the insert, delete and find process as well. This is the resulting tree: ...

c,command-line-arguments,binary-search-tree,stderr

argc will always be at least 1 because argv[0] contains the path to the executable. Therefore you should be checking if ( argc != 3 ) since you are passing 2 arguments from the command line. When you execute ./a.out main.c input.txt, argv[1] will be main.c and argv[2] will be...

java,stack-overflow,binary-search-tree

The reason that you encountered a StackOverflowError is that you inserted your items in an order that was already sorted. Let's see what happens in this case. I'll use integers, even though you have more complicated objects, for simplicity in seeing what happens. After inserting 1: Root(1) After inserting 2:...

data-structures,binary-search-tree,comparator

I am assuming that the left subtree contains elements smaller than the root and the right subtree elements larger than the root. To answer your second question first: it would be infix traversal. This first visits the left (smaller) child recursively, then the item itself, then the right (larger) child...

java,recursion,binary-search-tree,depth

Your depth method should return one if the current node is the one you are looking for or the depth of the next node down plus one if you need to keep looking. For example: N5 N3 N7 N1 N4 N6 You want to know the depth of N1. You...

c++,binary-tree,binary-search-tree

Tree *tree(int *a, int left, int right) { Tree *tree1 = new Tree; tree1->right_son = nullptr tree1->left_son = nullptr Or you could do same in the struct Tree by adding a contructor to the struct. ...

algorithm,data-structures,tree,binary-tree,binary-search-tree

Rather than jumping right into an algorithm that works here, I'd like to give a series of observations that ultimately leads up to a really nice algorithm for this problem. First, suppose that, for each node in the tree, you knew the value of the largest and smallest values in...

Well the minimum height is easy, just fill each level of the tree with nodes until you run out. That height is the minimum. To find the maximum, do the same as for the minimum, but then go back one step (remove the last placed node) and see if adding...

java,binary-tree,binary-search-tree,priority-queue

Top hit algorithms use a min-heap (PriorityQueue in Java), but there should be some size checking in your algorithm. Suppose each item has a score, and you want to collect the 10 items with the highest score. PriorityQueue efficiently exposes the item with the lowest score: PriorityQueue<DataObject> top = new...

java,algorithm,recursion,binary-search-tree,graph-theory

The algorithm you described is not acceptable because there can be at most 100 rows, so if in each row the number of nodes in the tree doubles, you'll end up with 2^101 nodes in your tree in the worst case. That problem can be solved by a simple dynamic...

algorithm,data-structures,tree,binary-tree,binary-search-tree

I'd call your understanding not quite correct. The big-O notation does not say anything about an exact amount of steps done. A notation O(log n) means that something is approximately proportional to log n, but not neccesarily equal. If you say that the number of steps to search for a...

c++,algorithm,vector,time-complexity,binary-search-tree

It can be done in O(n) time and O(logN) space by doing an in-order traversal and stopping when you reach the n/2th node, just carry a counter that tells you how many nodes have been already traversed - no need to actually populate any vector. If you can modify your...

Assuming your BinaryTree class is declared as template <typename T, typename U> class BinaryTree ... Add(T, U); I would guess you can only add a preconstructed queue BinaryTree<string, queue<int>> tree; tree.Add("foo", queue<int>()); // or queue<int> q; q.push_back(1); ... tree.add("bar", q); To modify the queue after it has been added, you...

You are using curr.compareTo(c)<0 (meaning "c is greater than curr") as the condition for putting c on the left of curr. I'm not sure exactly what you meant to write, but it would be the exact opposite of this. (Either flip c and curr, or change < to >, or...

Your recursive calls to printTree in the method should be self.printTree(). Default scoping is different in Python to C++ ! Whereas in C++ the default scope is the current object (*this) that is not the case in Python. The default (unqualified) scope is the same whether we are dealing with...

java,garbage-collection,binary-search-tree

Any object that cannot be reached by any live thread will be eligible for garbage collection. Based on that: Yes. No. Depends on the implementation of GC. Anyway, as a Java programmer, you can't control it. All you can do is have a trust that it will do its job...

algorithm,data-structures,binary-search-tree,prefix-sum

A treap with implicit keys can perform all this operations in O(log n) time per query. The idea of implicit keys is pretty simple: we do not store any keys in nodes. Instead, we maintain subtrees' sizes for all nodes and find an appropriate position when we add or remove...

Why we need sum of frequencies The idea behind sum of frequencies is to correctly calculate cost of particular tree. It behaves like accumulator value to store tree weight. Imagine that on first level of recursion we start with all keys located on first level of the tree (we haven't...

c++,pointers,vector,binary-search-tree,stxxl

Store iterators pointing to elements instead of pointers/refs to elements. Pointers/refs will be invalidated because of paging to/from the disk, but the iterators will not be invalidated. Ex: // Safe to store this, not safe to store &nodes[node_index]. stxxl::vector<Node>::iterator node_it = nodes.begin() + node_index; ... and const_iterator for read-only purpose....

c,data-structures,linked-list,binary-search-tree,traversal

The node structure presented in the question is the same as for a regular binary tree which is using names child and sibling instead of the traditional left and right. If you want to print a path to the desired node, you should print the root values of each subtree...

if ( !isdigit(c) && !ispunct(c) && c != '\n') name[i++]=c; That will include the whitespace at the end of the name. So you need to search for "Mark Ronson " (note whitespace at end). Or better still, you should write your code to not include that last whitespace in the...

c,recursion,binary-search-tree

To answer "which of the roots is actually returned" ... they all are. The question is where are they returned to and what is the final value. When you traced forwards through your code you saw where the recursive function call was executed and understood that you created a new...

java,binary-tree,binary-search-tree,static-methods

From an OOP perspective I believe approach number 2 is the way to go. (Statics are in general often frowned upon in OOP.) As I understand it, the method uses this as root, and then traverses the rest of the tree without calling any instance methods? This isn't too bad...

c++,arrays,binary-tree,binary-search-tree

Do like this... for(i = 0; i < k; i++) cout<<a[i]<<" "; Or like this i=0; while(i<k) { cout<<a[i]<<" "; i++; } The problem in your code is with while(a[k]) ...

c++,binary-search-tree,tree-traversal

This seems pretty much OK. You can't really improve the complexity of what you did, since the number of operations is linear. A few implementation points: Counting is a non-modifying operation, so you might want to consider consting some stuff. You've basically implemented on your own something similar to what...

c++,recursion,binary-search-tree

return will return from the current function, but of course where you return to, in a recursive situation, is the level below, so you may need to check the result and decide what to do, and not continue searching the other side of a tree, for example.

algorithm,split,concatenation,binary-search-tree,red-black-tree

In future. If any have the same problem again: Tarjan have some important differences in the algorithm compared to what Ron Wein does. I still haven't been able to see that Wein is correct in his algoritm, but Tarjan is. So I suggest you use his instead. First important point...

binary-search-tree,binary-heap

The answer is simple: You can't just dynamically change the size of an array. The size of an array can't just be changed afterwards. If you would use an array you'd have to enlarge it or shrink it depending on what is added or removed which would cause unnecessary overhead...

The Idea: You can do an in order traversal of the tree and keep track of the number of nodes you have visited. This requires a counter of some sort and probably a helper method. We stop searching when we find a node with a value greater than or equal...

c#,oop,data-structures,binary-tree,binary-search-tree

Visit: http://www.kerryr.net/pioneers/ascii2.htm Analyze the decimal equivalent of the alphabets. For example: if you want to compare "leopard" and "cobra". Take first characters of both which are 'l' and 'c', convert them into their decimal equivalent which should be 108 and 99 respectively. Compare them if 1st is greater than 2nd...

algorithm,tree,binary-tree,binary-search-tree,graph-algorithm

I guess this should do the trick: traverse(BinaryTree *root) { if (!root) return; cout << p->data << " "; if (root->left ) traverseL(root->left ); //special function for outer left if (root->right) traverseR(root->right); //special function for outer right } traverseL(BinaryTree *p) { cout << p->data << " "; if (root->left )...

java,data-structures,binary-search-tree

You are not associating the new subtree (let's call it "node" because it contains only 1 element) to the existing tree. You are creating the node, moving down the tree, and when you find that the current node is null associate the new node to the current. You got to...

data-structures,binary-tree,binary-search-tree

Figured out a skewed Tree is the worst case of a tree. ` The number of permutations of 1, 2, ... n = n! The number of BST Shapes: (1/n+1)(2n!/n!n!) The number of skewed trees of 1, 2, ....n = 2^(n-1) ` Here is an example I was shown: http://i61.tinypic.com/4gji9u.png...

c,data-structures,binary-search-tree

Where is the value of root coming from? You're not passing in the value anywhere? Also, it is tough to help when we don't know the design of type bst. It appears that you have the right idea. Create a node, and give it some data. If the root is...

c++,algorithm,sorting,binary-tree,binary-search-tree

I think the solution to your problem lies in the comment by @Praetorian: You probably want myfile << random_integer << '\n';. Otherwise stoi will throw out_of_range, which is probably the cause of the crash. I have a few generic suggestions regarding your function. Separate your function into two -- one...

insert,stack-overflow,binary-search-tree

Have you searched on Stack Overflow? :p Just kidding. The issue probably is the recursive call. A function call uses the stack to store register values, which are only removed from there if the called function ends and control is returned to the calling function. For recursive calls, all those...

c++,algorithm,tree,binary-search-tree

While deleting a BST node using recursion, you must track the root node, which you're doing correctly as root->left = // ... and root->right = ... However when call reaches to caller after unwinding the stack, the root may get modified ( case when you delete the root itself )...

c,binary-tree,binary-search-tree

a sample to modify like as void inorder ( struct btreenode *, int ** ) ; int* sort(int *array, int arr_size) { struct btreenode *bt = NULL; int i, *p = array; for ( i = 0 ; i < arr_size ; i++ ) insert ( &bt, array[i] ) ;...

algorithm,data-structures,binary-tree,binary-search-tree,avl-tree

How to find the order of one given element? The order of an element is its rank on the resulting sorted sequence. If assume we store the number of children in the sub-tree, we can assign virtual weigths to edges. Any edge going left weigtht 0. Any edge (x...

algorithm,tree,binary-search-tree,median

As you mentioned, it is fairly easy to first find the number of nodes, doing any traversal: findNumNodes(node): if node == null: return 0 return findNumNodes(node.left) + findNumNodes(node.right) + 1 Then, with an inorder traversal that aborts when the node number is n/2: index=0 //id is a global variable /...

algorithm,data-structures,binary-search-tree,red-black-tree,tree-balancing

Re-balancing may make a sibling of a node its new parent, but it can not change the relative order. Keep in mind that the red-black tree is a binary search tree and thus it should keep elements smaller than a given element in its left subtree and elements greater than...

algorithm,data-structures,binary-search-tree,red-black-tree

One solution is to maintain two trees; one where a == b and one where a != b. For most functions you will probably need to call in to both trees but this will end up as the same big-O complexity since 2*O(log n) -> O(log n).

java,recursion,binary-search-tree

I agree with the Wang's answer. The java program pauses the execution of 4 (as you are recursively calling the method inOrder(4->left) i.e. inOrder(null).Now, it does not enter the condition as it fails).Now, the execution of 4 resumes and prints out the value 4 and then continues. I hope this...

java,binary-tree,binary-search-tree

Perhaps the picture will help. I find recursion difficult as well, and I've found pictures useful. It might be nice to open the diagram in a separate window and have the explanation on the side. First of all, recursion uses something called a stack. It's the pile of four...

c,binary-search-tree,scanf,gcc-warning

scanf("Enter the node value: %d", &val); should be scanf("%d", &val); and scanf("Want to enter more: %c", &ch); should be scanf(" %c", &ch); Assuming you are intending to this printf("Enter the node value:\n"); if(scanf("%d", &val) != 1) { printf("Integer not read \n"); break; } printf("Want to enter more:\n"); if(scanf(" %c", &ch)...

python,python-3.x,binary-search-tree,nodes

To determine the parent of the node, set a variable initially to None. Now when you do your binary search of the node, set that variable to whatever node you were on previously and this variable should give you the parent once you find that node When you are...

You're printing an object, not its inner value (in other words, you're calling toString() implicitly). In order to print the value, you should get the value from Node object: System.out.print(focusNode.displayNode() + " "); Also I would recommend you to rename your displayNode() method to getValue(), as it is better explains...

java,recursion,binary-search-tree,spell-checking

The problem is likely not in your algorithm, which looks mostly fine, but in your error message System.out.println(sArray.get(mid) + " is possibly mispelled"); Did you mean System.out.println(key + " is possibly mispelled"); ? Regarding your binary search, the only concern that I have is that your highIndex seems to be...

If a node has no left or right node, you know that the deepest full level is 1 - the node itself. If it has left and right nodes, recurse and choose the smaller. highestFull(BinaryNodeX<Comparable> *t) { if ( ! t->left || ! t->right ) return 1; return 1 +...

c,struct,binary-tree,binary-search-tree

Arrays are not assignable and, by consequence, not implicitly copyable either. Even if they were, newNode -> s = *tempWord tries to assign a single char to an array. You will have to use strncpy (or memcpy) to copy over the array elements....

You can achieve this by recursive. public class TreeNodeDemo { List<Integer> values = new ArrayList<Integer>(); public List<Integer> storeKeyValues(TreeNode root) { treeTravel(root); return values; } private void treeTravel(TreeNode node) { if (node != null) { treeTravel(node.left); values.add(node.value); treeTravel(node.right); } } public static void main(String args[]) { TreeNode root = new TreeNode(4);...

recursion,binary-search-tree,inorder

Like all recursion*, the call stack contains the control for your operations as the recursive calls start to return - program control is returned to the point where your current_node pointer is set to the parent that you were examining prior to making the recursive calls. (* All recursion, unless...

The reason you're getting 12 is that your code returns twice the number of elements in the tree (of which there are 6). The fact that 12 also happens to be the first element is purely a coincidence. The return statement should read: return 1 + size(node.left) + size(node.right); i.e....

javascript,algorithm,data-structures,binary-search-tree

Your code has a provision for the case when the found node is the root and it is the only node in the tree, and if a node has both a left and a right child, you overwrite its value. But when the node to remove is the root and...

python,binary-tree,binary-search-tree

Your analysis is correct, the sample solution checks for None twice for each node and your solution checks only once, otherwise they are equivalent. I’d also say that your solution is more readable, but that’s somewhat subjective. As an enhancement, you can get rid of the first line in the...