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

haskell,recursion,tree,functional-programming,binary-tree

I think the problem is you're naming giving the inner nodes the same names so connectOutside connects the first names it finds (which happen to be the last nodes in your tree). You can solve this by giving each node a unique name depending on its position: diagTree :: Show...

A balanced binary tree is one where every leaf is no more than a certain amount further from the root than every other leaf node. For example, an AVL tree is a balanced binary search tree where: Its left and right subtrees are balanced. The difference between the depth of...

This is an excellent chance for you to learn how to debug your programs. I suggest you run the program in a debugger and see what the values of node and node->left is when the segfault happens. An access violation is when you are accessing memory that your program is...

c++,data-structures,binary-tree

For constructing left subtree range should start from l instead of 0. root->left=ConstructfromPreorderInorder(pre, n, in, l, key, k); instead of root->left=ConstructfromPreorderInorder(pre, n, in, 0, key, k); ...

recursion,lisp,common-lisp,binary-tree,binary-search-tree

The infinite recursion probably happens as part of the printing. You can avoid this by: Don't print the circular structure Enable circle-detection in the standard printer: (setf *print-circle* t) ...

java,algorithm,tree,heap,binary-tree

The issue was the fact that I reset size way too early. Here is the author's implementation of hasLeftChild() private boolean hasLeftChild(int index) { return leftChild(index) <= size; } private int leftChild(int index) { return index * 2; } By setting size to zero, and incrementing it for every pass...

algorithm,recursion,binary-tree

The algorithm you linked to is reproduced below, in case the link changes: public static Tree findLowestCommonAncestor(Tree root, Tree p, Tree q) { if (root == null) return null; if (root == p || root == q) return root; Tree left = findLowestCommonAncestor(root.left, p, q); Tree right = findLowestCommonAncestor(root.right, p,...

java,nullpointerexception,binary-tree

Your problem is, that you have more than one TreeNode instance, but only the outer one has writer filled. You can see in your stack trace that actually the outer writer was successfuly progressing to line 106, where it calls no.print(). This is another node object. And in this object...

java,generics,binary-tree,comparable

Make your Binary Tree generic like public class BinaryTree<T extends Comparable<T>>{ ... } Whenever creating a BinaryTree instance, specify the containied type: new BinaryTree<MyClass>(); Where MyClass must implement Comparable<MyClass>, i.e. be comparable to Objects of the same class. Your methods would read as (example): public Node lookup(T value) { ......

c++,algorithm,recursion,tree,binary-tree

I believe the intent is to take two sorted binary trees and combine them into a single sorted binary tree. The key is the comparison if(A->value > B->value). This branch ensures that the A parameter will always contain the lesser value at the point in which the subtrees are merged,...

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

Essentially, it's the same answer as your last post. right_old = findoldestn(n->right); left_old = findoldestn(n->left); then figure out the oldest one between left/right and current, and return that value. And that can be put in place with res = (right_old->age > left_old->age ? right_old : left_old); finalRet = (res->age >...

Pointer points to a memory location. After free() you are giving back the allocated memory back to OS. Accessing this memory is UB(Undefined behavior) So you might see expected result but since you have UB this is not guaranteed at all time. In you case let's say you free the...

java,arrays,arraylist,tree,binary-tree

The Arrays class is a util class, not the type you'd use for an array. The Arrays class never takes a generic argument, which is what your error is telling you. If you want an ArrayList that contains arrays, then you're probably looking for something like this: ArrayList<TreeNode[]> aList =...

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

binary-tree,avl-tree,red-black-tree

I believe AVL Trees actually satisfy your condition. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. http://en.m.wikipedia.org/wiki/AVL_tree...

python,class,python-2.7,tree,binary-tree

Your insertRight method inserts on the left: def insertRight(self, newNode): if self.rightChild == None: self.leftChild = BinaryTree(newNode) # ^^^^ As such, all your rightChild attributes will forever remain None. You should use is to test for None: def insertRight(self, newNode): if self.rightChild is None: self.rightChild = BinaryTree(newNode) else: t =...

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

Something like this will copy your Tree: def copyTree(t:Tree):Tree = { t match { case EmptyNode => EmptyNode case Node(left, right, value) => Node(copyTree(left), copyTree(right), value) } } ...

c,algorithm,binary-tree,tree-balancing

The basic idea is as follows. For insertions, you first insert your new node at a leaf exactly as you would for a non-balanced tree. Then you work your way up the tree towards the root, making sure that, for each node, the difference in height between the left and...

I'm going to talk about rooted subtree isomorphism; the unrooted case can be handled without regard to efficiency by trying all roots. The basic idea is that if you have trees A B /|\ /|\ / | \ / | \ / | \ / | \ a1 ... am...

First answer is right, but you always can use pointer to pointer, something like this. typedef struct Node { Node() { left = NULL; right = NULL; data = NULL; } struct Node* left; struct Node* right; char* data; } node; typedef struct BSP { BSP() { root = NULL;...

I think the issue is your recursion. Let's assume a really simple structure. A node with no left or right (both null). First, leafnode is null to begin with. Given the structure we can't go into the if-block. Given the flag==false, we can't go into the while loop. So you'll...

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

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

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

algorithm,recursion,binary-tree

Write a function find_saddle that takes a node, and the minimum value of the parents (defaulting to INT_MAX for the root node). It will return the value of the largest child. When the function is called, it figures out the largest value a child can have and potentially be a...

c,parsing,recursion,tree,binary-tree

The problem is that you need the recursive call to return both the newly created node and the updated input pointer. There are various ways of doing this, but the easiest one in C is to pass the input pointer by reference; or, in other words, pass a pointer to...

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

You never set self.root; you only rebound p. p is a separate variable, setting it will not set self.root. Without self.root set, your tree remains empty. Note that because None is a singleton, in Python you normally use is to test for the object. You made several other mistakes in...

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

python,list,recursion,binary-tree

I think that is because you didn't define the action when l[1] and l[2] are not none. So when you pass the argument to the function, it puts 'a' to the key of root, and find that none of the conditions defined matched, then the function exists without doing any...

if self.left is None or self.right is None: if one of them is None, return 0 you need to at least get the size of the right + 1 if left is None I think you need something like : leftSize = self.left.size() if self.left else 0 rightSize = self.right.size()...

java,nullpointerexception,binary-tree

The root cause is that in Java arguments are passed by value, which means, when you pass a (reference to) node n as an argument, you're actually passing a copy of the reference to that node, which is null at that time. Since you're changing the copy-reference, nothing is really...

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

Here's the solution: It was generated from this Python code, using python tree.py | dot -T png a.png data = """ 40 A1 41 00 42 00 43 B2 44 00 45 00 46 D4 47 49 48 00 49 C3 4A 00 4B 00 4C E5 4D 43 4E...

A C / \ / \ B C A D \ / D B It seems these trees both gives: null, B, null, A, null C, null D, null. But it's possible to save a binary tree of depth N in array of size 2N-1. A C / \...

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

It looks like you are trying to "fold" adjacency lists into a single hash table. That's possible, but you need to change the type of the element to something capable of holding two integers. The most common approach would be using a TreeNode class: class TreeNode { private final int...

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,algorithm,recursion,binary-tree

As I mentioned in my comment above, if you did an iterative post-order traversal, you'd get nodes in the order: 3, 4, *, 4, 2, /, +. From this, you'd simply need a stack to evaluate the expression. Push 3 Push 4 Push (pop() * pop()) Push 4 Push 2...

c++,data-structures,binary-tree,ternary-operator

The ternary conditional operator is an operator that combines multiple expressions into a larger expression. break is a statement and not an expression, so it can't be used inside a ternary conditional expression. You could, though, rewrite your code like this: while (current->left != nullptr) current = current->left; Hope this...

java,recursion,data-structures,binary-tree

TestMain.Java public class TestMain { public static void main(String[] args){ BinaryTree btree = new BinaryTree(); btree.insert(1); System.out.println(btree.getRoot().getData()); } inside BinaryTree: public BTNode getRoot(){ return this.root; } private void insert (int data, BTNode rootParameter){ // your problem is here //case 1: no element in binary tree if (root == null){ //...

scala,sum,binary-tree,immutability,case-class

Using a List is not a good idea for the reason that when you concatenate two lists, you will have to copy their content so an O(n) complexity operation each time you encounter a Node. If you really want to do it with Lists, you could do it like this:...

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

There is a mistake in the definition of your isElement function: you're calling leftTree twice, instead of calling both leftTree and rightTree. As a result, right subtrees are never explored. Amend the code accordingly, isElement tree t |isNode tree == False = False | nodeValue(tree) == t = True |...

Notice the line: root->left=insert(root->left,val); Here you are assigning the result of insert() to root->left. You need insert() to return a node* pointer here, or else we would have no idea where malloc placed the new node in memory, and so you wouldn't be able to add the node to the...

If you make every node in the tree store a pointer to it's first child and a pointer to it's next sibling then you have a binary tree representation of your m-ary tree.

java,arrays,binary-tree,inorder

myTree.inorder(0); // parameter : 0 inorder((node * 2)); // node = 0, node * 2 = 0, Therefore, the parameters will continue to be zero is an infinite loop. public class BinaryTree { char[] tree = {'k', 'q', 'r', 'g', 'e', 'i', 'y', 'p', 'l', 'b', 'x', 'm', 'g', 't',...

Yes there is, but it will also require adding some more data to treeNode, a pointer to the list node (if such exist). Now, the idea is once you have found where to add the new node (v), and let's say it is a son of some node u. 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. ...

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

visual-c++,c++-cli,binary-tree

Because String.Copy is static method, I believe. It returns back string which is not assigned to value field anywhere in you code Something like newNode->values = String::Copy(s); might work...

The problem is that you pass a copy of a pointer to a read_tree function. That is, when you call read_tree(r) in the main function, r remains NULL regardless of what happens inside the read_tree function. You can fix it by passing a pointer by reference. That is, changing read_tree(Nod*...

algorithm,data-structures,binary-tree,inorder,preorder

Start with the preorder traversal. Either it is empty, in which case you are done, or it has a first element, r0, the root of the tree. Now search the inorder traversal for r0. The left subtree will all come before that point and the right subtree will all come...

You can't delete your root node because your code is missing an else statement after your inner if / else if / else if statements. That means that you are not covering all cases (tree with a single node is one such case). Right after else if(item.right != null) {...

algorithm,tree,binary-tree,red-black-tree

This is fine. Red-black trees are balanced, but not necessarily perfectly. To be precise, properties of red-black tree guarantee that the longest path to the leaf (implicit, not shown in your picture) is at most twice as long as the shortest. Shortest one has length 2 (2 -> 1 ->...

algorithm,recursion,binary-tree,non-recursive

I have find a solution by using recursive /** * recursive */ public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> rst = new ArrayList<List<Integer>>(); helper(rst, new ArrayList<Integer>(), root, sum); return rst; } public void helper(List<List<Integer>> rst, ArrayList<Integer> list, TreeNode root, int sum) { if (root == null) { return; }...

In the spirit of @lifus' answer, but avoiding mutable state, you can use the function return to set maxLevel public static void rightView(TreeNode tNode){ int maxLevel = 0; rViewUtil(tNode, 1,maxLevel); } public static int rViewUtil(TreeNode tNode, int level, int maxLevel){ if(tNode==null) return; if(maxLevel < level){ System.out.print(tNode.value + " "); maxLevel...

You have a compile error because you don't always return something : if(root.getLeft()!=null){ search(root.getLeft(), node); } if(root.getRight()!=null){ search(root.getRight(), node); } This would fix the compile error but not the algorithm : if(root.getLeft()!=null){ return search(root.getLeft(), node); } if(root.getRight()!=null){ return search(root.getRight(), node); } This should fix the algorithm : if(root.getLeft()!=null && search(root.getLeft(),...

Make the return type void and remove return result. There's no need to return the result object, since it's the same result object that was passed in (the caller already has a reference to it).

Assuming you have a tree node class that has a string value attribute, and attributes to store its left and right children, the implementation would be fairly simple: class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def find_max(node): if (node is None):...

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

c++,algorithm,stack,binary-tree,xor

It is helpful to think in terms of the tree structure and recursion, and recognise that pre-order, in-order and post-order traversals are three instances of a recursion on a tree. Since this is a homework, IMO the real question you should be asking "How can you simulate recursion with a...

java,recursion,binary-tree,nodes

I suppose the problem comes from if (node == null){ root = newNode; } You are traversing the tree and in the last step you are asking the left/right child of a leaf node. This hasn't one, so it's child is null. This is the value returned by the recursive...

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

There are several issues here: Your node allocation should go inside the conditional block in insert, otherwise you allocate memory for null nodes. You should initialise the left and right pointers to NULL in case the node is a leaf node and has no children. Most important. You changes to...

Here's the relevant part of your code: void insertNode(NODE *r, int key) { r = newNode; //inserted return; } Your parameter is a copy of the pointer you've passed. The assignment changes that copy, but not the argument to the function. The copy then gets immediately destroyed by the return....

c,function,pointers,malloc,binary-tree

You set root to NULL: ramo *root=NULL; then pass a copy of it to creaAlbero(): creaAlbero(root, 1); which modifies the copy root = malloc(sizeof(ramo)); then returns. The original root is still NULL, because nothing changed it. Consider returning root from creaAlbero(): ramo * creaAlbero(int n){ printf("%d\n",n); ramo *root = malloc(sizeof(ramo));...

algorithm,binary-tree,tree-traversal

This is the first algorithm that comes to mind. Assuming that you have an array that stores the values in nodes node_value[NODE_NUM], where NODE_NUM is the number of nodes in your tree, and you store index of childs of each node with the arrays left[NODE_NUM] and right[NODE_NUM], and your root...

c,algorithm,tree,binary,binary-tree

You should be doing something like: int total_depth(tree_t *tree, int accum) { if (tree == NULL) { return 0; } return accum + total_depth(tree->left, accum + 1) + total_depth(tree->right, accum + 1); } total_depth(root, 0); ...

php,tree,binary-tree,breadth-first-search

I wrote BFS search function myself. I used PHP's SplQueue global variable to store array of children. Private $queue = []; function for BFS public function traverseTree($rootNode, $dummyQueue) { if($rootNode->lft != 0) { $dummyQueue->enqueue($rootNode->lft); } if($rootNode->rgt != 0) { $dummyQueue->enqueue($rootNode->rgt); } if(!($dummyQueue->isEmpty())){ $nextId = $dummyQueue->dequeue(); $nextNode = //get next node...

c++,recursion,binary-tree,nodes,children

You can scrunch down your logic and make it a bit more straightforward by implementing a function to return the number of children given a node. template <class elemType> int nodeSize(nodeType<elemType>* node) const { int count = 0; if (node->lLink) ++count; if (node->rLink) ++count; return count; } template <class elemType>...

php,data-structures,binary-tree,binary-heap

I think the error in your check: if ($key != count($heap)) { echo $heap[$key*2+1]; echo $heap[$key*2+2]; } Here may be a situation with $key*2+2 is out of bounds the array. Add the check for it too. Try to use bool array_key_exists ( mixed $key , array $array ), something like...

Just use the formulars here and here (german text but you only care about the formulars so it should be ok) and you get this: Σk=1,...,n-2 ( Σi=1,...,k i ) = Σk=1,...,n-2(k⋅(k+1)/2) = 1/2⋅Σk=1,...,n-2 k²+k = 1/12⋅(n-2)⋅(n-1)⋅(2n-3) + 1/4⋅(n-2)⋅(n-1) and you can simplify it to 1/6(n-1)³ - 1/6n + 1/6....

public class BinaryTree{ private BinaryTree right; private BinaryTree left; private String data; public BinaryTree(String s){ data = s; right = null; left = null; } public void setLeft (BinaryTree l){ left = l; } public void setRight(BinaryTree r){ right = r; } } Your question suggests that the tree should...

haskell,functional-programming,binary-tree

Infinite data structures can generally be defined by functions which call themselves but have no base case. Usually these functions don't need to pattern match on their arguments. For example, a list equal to [1..] can be written as infiniteList :: [Int] infiniteList = go 1 where go n =...

We can use dynamic programming. Let: d[i] = longest path with at most one turn node such that i is the turn node d_up[i, dir] = longest straight path from i to one of its ancestors coming from direction dir d_down[i, dir] = similarly, except going to descendants. We have:...

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

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

The problem is that the root node is passed to the add method by value and not by reference. Java passes objects by value and not by reference. Check out the link below for further explantion Is Java "pass-by-reference" or "pass-by-value"?. Modify the add methods of your code as follows...

java,recursion,binary-tree,nodes

public Node { int data: Node left; Node right; } int countChildren(Node head) { if(head==null) return 0; return ((head.left == null) ? 0 : countChildren(head.left) + 1) + ((head.right == null) ? 0 : countChildren(head.right) + 1); } This is my suggestion....

algorithm,data-structures,binary-tree

You appear to be looking for integer sequence A001699, "Number of binary trees of height n". One possible algorithm to generate them being: a(n+1) = 2*a(n)*(a(0)+...+a(n-1))+a(n)^2 Unfortunately, there doesn't seem to be a closed-form version. Each formula is itself recursive, or uses A003095, which is also recursive....

I was running wrong tests. Same code logic will work in Java as well as rightly pointed out in comments that pass by value does not make a difference because value is getting returned. The following is the working Java Code: public static int sumTree(TreeNode node){ if(node == null) return...

You're just assigning new Node(p) to a local variable node, whose value is lost as soon as the function returns. To change the existing tree, your assignment should have the form node.left = new Node(p); or node.right = new Node(p).

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++,linked-list,binary-tree,levels

Here is the solution of above problem. I am putting the complete code. #include <iostream> #include <list> using namespace std; struct Node{ Node *left; Node *right; int data; Node(int d) { left = NULL; right = NULL; data =d; } }; class Binary_Tree{ Node *root; list<list<Node*> > level(Node*); public: Binary_Tree()...

Each node has a weight value equal to the length of its string plus the sum of all leaf nodes' weight in its left subtree... A has no right subtree so its value is the sum of the weights of all the leaf nodes (even if A had a...

Using the link: Deleting Leaves From a Binary Tree I have found the errors in my code and corrected them using the answer given in the link. Correct Code as follows: private BinaryNode pruneLeaves (BinaryNode p) { // There is a left child if (p.left != null) if (isLeaf(p.left)) //Is...

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

There is no such feature in C++ (as of 2015, hence including all standards up to C++14). However, Bjarne Stroustrup has written a proposal to add default comparison operators to the standard. What this essentially does is generating a comparison operator for you, in case you don't declare these operators...