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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

If you want to take a look at a robust implementation of BST, here's one: http://algs4.cs.princeton.edu/32bst/BST.java.html Also, if you'd like to actually understand what and why is going on there, I suggest looking/reading courses there as well. Edit: Well, first of all, let's address a few issues here. Looking at...

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

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

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

Here is an example of a generic tree destroy: // GenericTree.h void genericTreeDestroy(void *treeNode, void (*fUserFree)(void *)); // GenericTree.c typedef struct TREE_NODE { struct TREE_NODE *left; struct TREE_NODE *right; }; void genericTreeDestroy(struct TREE_NODE *treeNode, void (*fUserFree)(void *)) { if (treeNode->left) genericTreeDestroy(treeNode->left, fUserFree); if (treeNode->right) genericTreeDestroy(treeNode->right, fUserFree); if (fUserFree) fUserFree(treeNode); free(treeNode);...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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