# Tag Info

## New answers tagged tree

2

The main piece of advice I feel I can offer is to avoid using the asterix from list2BST import * This makes it much harder for other users to work out where individual functions are coming from. It is much better practice to say import list2BST and then list2BST.<function name> or from list2BST import <function_1>, <function_2> I ...

2

Don't import the standard namespace Namespace std is a large, and growing, namespace. Do you know every identifier in it? Including the ones to be defined in C++20 and beyond? Bringing all its names into the global namespace not only eliminates the benefits of using namespaces, but also has the potential to silently and subtly change the meaning of your ...

3

Stop using namespace std; Having using namespace std;, especially in a header file is considered bad practice. This Stack Overflow post explains the reasoning quite well. In your case it's especially unnecessary since you do not even use something from this namespace in BST.h and only std::string in Packet.h. Unnecessary includes Again BST.h. There are a ...

5

You seem to make use often return 1. It would be better to use booleans to show a clear intention of what you want to return. Also, your hash_route, which you build as a dict, has a constant value that is never used, making it effectively a set, which is fine if all you care is the lowest common ancestor. I would go for: def traverse_DFS(root, ...

7

Code readability and style Your code has nothing wrong with style (as far as I know). It seems to be (99.9999...%) PEP 8 compliant. I ran a PEP 8 checker over your code and this is what it picked up - Which basically tells you to add a space before the operator '=' here - hash_route= {} # hash_route = {} As for the missing newline at the end of the ...

5

Your Queue class should be replaced by the builtin collections.deque which offers better performances (lists .pop(0) are $\mathcal{O}(n)$ since the remainder of the list have to be shifted, but deque.popleft() is $\mathcal{O}(1)$). You should also take the habit of opening files using the with statement to avoid keeping opened file descriptors around: ...

6

I'm a little bit short on time at the moment, but I'ld like to share a few minor observations with you. Maybe I will also find time to look at performance related optimizations and expand it later. You said you would like your code to be Pythonic. With that in mind you could replace print(list(reversed(values))) by print(values[::-1]) which uses slicing (...

3

successor(node, targetValue) does not necessarily return the in-order successor even if called with a node in a valid search tree and that node's value: what about search trees where a value can occur more than once? I notice no docstrings. successor() in a binary tree (I could guess that much from left and right) might be the in-order successor, ...

4

For idiomatic Python: You should not put spaces between the brackets and the values in function calls. You should use snake_case for variables. You've said you have concerns over finding the parent node that is the ancestor. Lets say we have the tree: A B C D Since that all left nodes are smaller than the current value in binary trees we know that $... 3 Some suggestions: You can use sys.argv or argparse to pass the size on the command line. The latter can check the type and range for you, and print an appropriate error message and usage string. You can specify a validator function in the type argument to check for non-trivial values. print_tree does not print the tree, it returns a string representation of ... -1 I defined a Higher-Order function: @tailrec def foldAsc(op: Node => Node): Node = { op(this) // <= still this statemnt when x=>x is useless.. parent match { case None => this case Some(x) => x.foldAsc(op) } } def asc(): Node = foldAsc(x => x) def ascVisited(deltaInc: Inc): Node = foldAsc { x => visited += ... 4 Please read over PEP 8 as your naming style is unidiomatic, and would cause programmers to be confused when seeing your code in the wild. I would move getting and setting a node by index into their own functions. if self.value >= 0 only hinders your code, the value -1 is perfectly valid in binary trees. It also means that you're limiting value to types ... 3 Clarification (OK) After update of your question, it has gotten clear that: you work on a DAG, which includes a Tree both your strategies DFS and BFS are in Pre-Order => original answer requesting clarification from the OP Review Definitions Before being able to review your code, I would like to review your definitions. Perhaps you should clarify your ... 4 There's a problem with your approach: it always visits all nodes to build value lists, even when the trees aren't similar at all. By obtaining leaf-node values lazily, you'll prevent a lot of unnecessary traversal work if the trees are different. This can be achieved by changing DFS to a generator method (using yield), and comparing the results with ... 2 In LeafSimilar, you could replace the manual comparison of the list elements with: return tree1.SequenceEqual(tree2); In DFS, I would call the parameter node instead of root, to avoid confusion. 3 Memory Leak std::shared_ptrs free their target when the last reference to that target disappears. Since you have Nodes that point at each other (node->right->parent == node) that never happens. std::weak_ptr is made to solve this problem. Ownership vs Pointing You are not forced to use std::shared_ptr just because you want to point at it from ... 2 Let's start with a bug: If a node has a right but no left child then the right subtree is traversed twice. As an example, the tree // 1 // \ // 2 // / \ // 3 4 return B(1, nil, B(2, B(3), B(4))) produces the output [1, 2, 3, 4, 2, 3, 4] The reason is that for the (empty) left child of node ①, the right child node ② is ... 3 Awkward API It seems strange to initialise a Solution object with various info that we provide again in the call of the method find_words. Actually, looking for places where self is used makes it pretty obvious: the instance is never used. It is a good occasion to watch the Stop Writing Classes talk from Jack Diederich. To be continued ? 2 Data Structure You don't have a Tree of nodes; you have a List of nodes which describes a tree-like structure in a serialized format. This is fine for storing the tree of nodes in a flat database table, but it is not a Tree. Traversing a Tree can be done in$O(N)\\$ time. Your Depth-First-Search traversal of the List of nodes requires searching the list ...

2

Here is what I understood from your question. I'm still unsure since you didn't provide a detailed description about how the input is transformed into the output, and why some elements do not appear in the output. Given: A list of element types A utility function that calculates a value for an element, given its index and type Calculate a sublist of the ...

1

Data Model I would add a restriction on the attribute and move the convenience method from the creator to this class. [AttributeUsage(AttributeTargets.Class)] class ParentAttribute : Attribute { public ParentAttribute(Type type) { Parent = type; } public Type Parent { get; private set; } } [AttributeUsage(AttributeTargets.Class, AllowMultiple=...

5

Prelude I'm using the static member Depth to keep track of how deep the visitor has gone. Could it be problematic having state on my extension methods static class? It would be uncommon. In fact, I wouldn't use extension methods to begin with. Tree walking should be performed by a dedicated tree walker. Would the SurveyPart abstract class make ...

4

Review Keep in mind I am using an older version of .NET so my semantics can be somehow verbose. Navigation You are lacking a reference back to the parent, which makes bottom-up navigation much harder. A tree that knows its parent allows for much more flexibility in navigation. root.children.Add(new Tree() { id = node.id, text = node.text, ...

2

Proposed Solution public static JObject ModifyDoubleIntegers(JObject source) { if (source == null) return null; var target = new JObject(source); var properties = target.DescendantsAndSelf().Where( x => x.Type == JTokenType.Float).Select(x => x.Parent).OfType<JProperty>(); foreach (var property in ...

Top 50 recent answers are included