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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

c,tree,malloc,binary-tree,free

There is confusion here: // Definition of a tree struct Tree { NodeP root; }Tree; // Definition of a node struct Node { int data; NodeP L, R; }Node; The definitions above define variables, not types! There is a bug here: TreeP newTree() { TreeP tree = (TreeP) malloc(sizeof(TreeP)); tree->root...

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

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

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

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

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

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

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

If I understand what you want to do is something like case Leaf(v) :: rs => sums(xs, acc+v) ...

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

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

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

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

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

python,algorithm,recursion,binary-tree,combinations

Building on ideas above....Here is python generator code to produce all equivalent orderings. import collections Node = collections.namedtuple('Node', ('root','left', 'right')) def tree_from_list(lst): if not lst: return None root = lst[0] left_lst = [x for x in lst if x > root] right_lst = [x for x in lst if x...

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

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

binary-tree,ternary-operator,data-conversion

I came up with something like this using trees. Not tested thoroughly: When I see a '?', it's my left child, so add to my left and go left. If I see ':', then: Go to my parent If right is not null and parent is not not null, keep...

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

Your problem is that your first function takes a Tnode **, that is a pointer to a pointer, and modifies the TNode * it points to. Your second function takes just the pointer, and modifies the passed-in argument; the caller can't see those changes, and so nothing is ever added...

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

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

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

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

I'm not sure if I understood correctly, but this is what I thought of. Basically, you can store the nodes in the tree as elements of an array/list. For arrays, think of something like this: public class Node { public int data; public int left; public int right; ... }...

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

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,algorithm,binary-tree,complexity-theory,space-complexity

You are storing the all the nodes that lie on the path from the root to a particular leaf in the List. If the binary tree is height balanced or it is a full/complete binary tree, the worst case time and space complexity is O(log n), where n is the...

Not with immutable case classes. It is a circular dependency: you need the parent to create the children, but you also need the children to create the parent. On the other hand most tree traversal algorithms don't really need the parent as the parent is usually on the stack...

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

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

Program is 90% correct. Here are your problems: strtok() uses some static buffer. It will always return a pointer to the same region of memory. This is why you feel like your top node changes every time. Just duplicate the parsed strings as well. you forget to initialize the count...

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

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

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

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