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,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...

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; } ...

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,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...

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...

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.

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....

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...

haskell,functional-programming,binary-search-tree

foldr has type (a -> b -> b) -> b -> [a] -> b, which means it expects a function of type a -> b -> b as its first argument. In your particular example, that translates to Integer -> BST Integer -> BST Integer, which is different than insert's...

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,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...

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)...

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) ...

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...

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,...

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....

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...

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

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,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...

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...

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...

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...

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...

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...

algorithm,tree,binary-search-tree,complexity-theory

Your current inorder traversal using recursion to perform the task. That makes it difficult to run more than one at the same time. So, first I would re-write the method to use an explicit stack (example here in C#). Now, duplicate all of the state so that we perform traversals...

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...

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...

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...

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...

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);...

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++,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...

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...

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...

haskell,binary-search-tree,timing

The last do block is not formatted correctly. Here is a diff: @@ -78,9 +78,7 @@ then return () else ioError e Right inpStr -> - do - let my_list = make_int_list inpStr; - my_time <- test_func my_list - putStrLn ("Execution time in Sections: ") - print(my_time); - return ();...

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: ...

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...

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...

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...

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...

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...

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,arrays,binary-search-tree

For your set of unvisited cities consider either a HashMap<String, City> or a HashSet<City>. In either case the lookup cost is constant (i.e. O(1)) which is better than O(log(n)) for large enough n. A common way to implement the Dijkstra algorithm uses a heap of nodes, ordered by cost. In...

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,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...

insertNode() takes a copy of the pointer, so changes made inside the function have no effect on the actual pointer in the tree. What you want to do is take a reference to the pointer: void insertNode(int data, Node*& head) ...

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...

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...

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,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,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...

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

With an unbalanced tree: 1 \ 2 \ 3 \ 4 \ 5 \ ... Your intuition of cutting the tree in half with each operation no longer applies. This unbalanced tree is the worst case of an unbalanced binary search tree. To search for 10 at the bottom of...

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...

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++,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...

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...

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,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...

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...

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.

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...

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...

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 +...

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...

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...

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...

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...

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:...

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...

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); } }...

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...

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...

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. ...

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...

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 )...

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...

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...

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...

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...

java,algorithm,recursion,binary-search-tree

There are three main possibilities when you try to remove data from your Binary Search Tree: data is less than the current node value: Call remove on the left subtree or throw a NoSuchElementException if it is null. data is greater than the current node value: Call remove on the...

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]) ...

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++,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.

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,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

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,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,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 /...