# Tagged Questions

The tag has no usage guidance.

36 views

### Extract All Possible Paths from Expression-Tree and evaluate them to hold TRUE

This is a follow-up question of my previous one: http://stackoverflow.com/questions/38421950/better-class-structure-for-logical-expression-parsing-and-evaluation Brief introduction: rules as ...
39 views

### How to describe a set of paths in a graph with as few nodes as possible?

I have modeled a problem as a graph that consists of many trees. Some of the nodes in the graph may belong to more than one tree. I am trying to describe a subset of paths in the graph with as few ...
16 views

### Randomly sampling chunks of a tree

I have a (non-binary) tree from which I want to sample various leaf and non-leaf nodes semi-randomly. The tree is generally less than 50 leaf nodes in all. The criteria for sampling is somewhat fuzzy ...
161 views

### Perform crossover operation on AST in genetic programming

So in general when you perform a crossover in GA, you directly flip a random section in the "genome", with the corresponding section in the other parent, and mutate it based on the mutation rate. ...
126 views

### BST to AVL in O(n) [closed]

I found in different places on the internet how to turn a Binary Search Tree into an AVL tree in O(nlog(n)). I was wondering how can this be done in O(n) (as the worst case limit). It kinda seems ...
72 views

### Matrix multiplication range queries

I have a huge list of matrix i.e A = {M0, M1, M2 .. Mn}. I have a task to find the product of all the matrices in a given range {x,y} i.e Mx * Mx+1 * Mx+2 ... * My. I would like to know if there is ...
67 views

### Keeping track of the number of nodes in the subtree in black and red trees

I was wondering, if I have a black and red tree and I want to keep track of the number of nodes in the subtree, what is the most effective way to do so? I mean how do I work with these values while ...
417 views

### Can a tree be used to create a stack?

I'm aware that linked lists, sets and arrays can be used to create stacks by themselves. The theory behind it is this linked-list: In some languages, a linked-list is substitutable for an array. ...
89 views

### Decision making algorithm

I'm currently solving an optimisation problem of my own design, just to experiment and learn a little something. Here's the concept: I have a user that starts at home. The objective of this user is ...
77 views

### Retrieving an incorrectly stored tree data structure

Way back in the hazy origins of our platform it was decided that we were going to need some hierarchical data structures stored in the RDBMS. The relationships between nodes were stored via a '...
227 views

### Algorithm to get all paths in a tree

I have a tree that has n-levels. For example here I have four levels: Each node has two children (except for the last one), however everyone except for the first and last node of each row has two ...
363 views

### What would be a good approach to generate a tree of folders?

Say I have an array of strings, like this: var folders = new[] { "Foo", "Bar", "Foo\Bar" "Foo\Bar\Baz" }; And that I have an object that represents a folder - something like this: ...
163 views

### Suggestions for structuring complex json structures?

I can't find many tips for how to design complex json structures beyond the obvious tips of not trying to nest too deeply, using defined data types, etc. For example, if I have a location that needs ...
152 views

### Is this Red-Black tree insertion pseudocode from Introduction to Algorithms (CLRS) correct?

For the Red-black tree insertion fixup the book distinguishes between 6 cases, 3 of which are symmetric. The cases are (z is the node being inserted): Case 1: z's uncle is red Case 2: z's uncle is ...
60 views

### Why do we have the “running” state in behavior trees?

I'm following the paper: Towards a Unified Behavior Trees Framework for Robot Control and attempting to implement my own behavior tree. I believe that I have the correct logic working for the main ...
123 views

### Finding xor sum in a tree

I was trying to solve this problem on hackerearth where you have a tree with values on each node and you have to answer queries that ask what is the xor sum between two nodes. Also, there are updates ...
78 views

### Abstract Syntax Tree with parent or not? [closed]

My question is as simple as the title says -- should I implement AST with parent or not? Currently I implemented it with parent -- the benefit of that approach is, that whatever I use, I can go up or ...
98 views

### MInimum tree coverage

I would like to understand what would be the optimal method of finding minimum tree coverage of tree nodes. Let me explain. I have a self-referencing structure that represents a tree, with a limited ...
93 views

### What's the name of the algorithm to balance an acyclic graph?

Algorithms class was a such a long time ago and I can't remember the name of the algorithm to balance an acyclic graph. Let's start with a graph that looks like this: 1 | 2 ...
82 views

### How can I roll-back the execution of a constructor while building a complex data structure?

I'm building a complex tree of objects. There are a total of five types, A, B, C, D, and E. There is a single instance of A, which is the root node. A has one or more Bs as children, each B has one or ...
96 views

### Bus bunching simulation code [closed]

I'm having a peculiar issue to solve. What I am supposed to implement is a bus transit simulation in which there are passengers coming at some random generated time intervals and are added into a ...
264 views

### Does a tree node have an ancestor?

Below is a rooted tree, where any node C except root has one parent P Ancestors of a node C are the nodes on path from C to root, including P,P's parent,P's grandparent, .... till root. My ...
425 views

### Implementing a Forest Data Structure in Java

Name of data structure that's tree-like with multiple root nodes I stumbled upon someone's answer to a question regarding implementing a tree that has > 2 nodes above. I just wanted to get ...
103 views

### Finding Parent Node in Directed Acyclic Graph

I've implemented a structural sharing algorithm for creating Clojure style persistent trees, but it relies on the child node knowing its own parent. function fork return new Node children: this....
84 views

### Big-O for Immutable Trees

How would you calculate the time and space complexity for a tree algorithm that creates a copy of a tree, but reuses as much of the original tree as possible? For example, A /|\ B C G /|\ D ...
201 views

### How to find the closest right neighbour in a tree?

Given a class: public class Node { public List nodes[]; public Node right; //NULL for now } What's the best way to fill the "right" element of all tree nodes? N ...
202 views

### Detecting surface faces of a huge 3D mesh/grid

I've written a module in my application that creates a mesh from existing coordinate and face data. The number of vertices in the mesh could easily exceed 10 million and the same goes for the faces. ...
134 views

### What method should I use to populate a tree as I'm consuming data that is contained within the tree?

I have a tree that consists of 5 types of nodes - V, W, X, Y, and Z. V represents the root node, and a given tree has exactly one element of type V. A V contains one or more Ws, a W contains one or ...
160 views

### Efficient algorithm for hierarchical traversing? JSON hydration, for example

I'm writing a small library that helps you hydrate JSON data into objects. Given this JSON example: { "date": "1970-01-01 00:00:00", "foobar": "baz", "user": { "name": "foobar", ...
174 views

### What is the time complexity of this program?

An algorithm is given on GeeksForGeeks.com for constructing a Binary Search Tree from its preorder traversal. They say that the time complexity for the following code is O(n^2). But in my opinion it ...
150 views

### Algorithm to go from infix notation to a tree

I've been trying to figure out an algorithm to go from an infix equation to a syntax tree, like so: (1+3)*4+5 + * 5 + 4 1 3 However, I don't just want it to handle operators, I ...
148 views

### Clean Abstract Syntax Tree

I'm writing a toy compiler for fun. Basically, my problem is that I don't want to clutter the AST with stuff like debug information (symbol tokens, locations of tokens, etc) as well as data that the ...
340 views

### Is this data model a list or tree?

Using python syntax with below environment diagram, teacher taught us that there are 11 trees(orange boundary) in this diagram, including leaf. It has been taught here, lists are represented as a ...
260 views

### Finding the optimal root

I am trying to solve a quora hackathon challenge question. The question descrpition is as follows : For the purposes of this problem, suppose Quora has N questions, and question i (1≤i≤N) takes ...
111 views

### Best way to traverse data and update nodes in Mongo DB

I am using Angular Tree View in my web app. Data coming from the server is build with https://www.npmjs.com/package/mongoose-materialized getArrayTree() function. What I need is, syncing the ...
390 views

### Expandable alternative to Visitor pattern for tree traversal?

I have a tree containing various subtypes of the my base node class. I now want to traverse this tree and do something with the nodes depending on their type. The most straightforward idea is to just ...
141 views

### Graphs and minimum spanning trees?

I am having a hard time finding information on how Graphs and spanning tree's work and how to construct/structure them. The reason is that I'm using a Delaunay Triangulation algorithm within the ...
44 views

### Advice on paging tree structured data

I'm in the process of building web based a commenting system, for which the comments are rendered in a reddit / disqus style tree structure. The MySQL schema uses a string of ancestor id's, and the ...
140 views

### Decision tree (?) reduction

I need to check certain conditions (of size n) on an object and perform one of several options available (size m) based on the result. Seems to me it fits a tree. Now. The tree is quite large and I ...
361 views

### Difference between sibling lists, left-child right-sibling binary tree and doubly-chained tree

The Wikipedia page for suffix trees descibes sibling lists as Each node has a pointer to its first child, and to the next node in the child list it is a part of. Wikipedia describes left-child ...
129 views

### Any good data structure to perform efficient lookup and modification operations about what are the shapes containing the current cursor position

I think I'm facing a pretty common issue but cannot remember which solution is the most suitable one. Let's put it that way: I can, in a, certain, given, language get some events anytime the user is ...
281 views

### Non-fixed-size Fenwick Tree implementation

I'm planning to implement a non-fixed-size Fenwick tree. That is, a Fenwick tree that allows interleaving range queries with adding/removing elements. All implementations and samples I've seen so far ...
220 views

### Is this Wikipedia pseudocode for in-order generic tree traversal correct?

Wikipedia states that the following algorithm works for any tree (not necessarily binary trees) Perform pre-order operation For each i (with i = 1 to n) do: Visit i-th, if present ...
168 views

### component-based power system for a game [closed]

My issue is that I've been trying to implement a power/electrical system for a while now. I'm using Unreal Engine 4 with C++ but that's not really relevant. I'm trying to implement some sort of ...
1k views

### How to determine whether two trees (not necessarily binary) are isomorphic

Two ordered trees T' and T'' are said to be isomorphic if one of the following holds: ◦ both T' and T'' consist of a single node ◦ both T' and T'' have the same number k of subtrees, and the ith ...
170 views

### Injectable, Poppable Stack

Background A project involves converting a relational expression map (rxm) to an XML/SQL statement. The map resembles: root > people, # "root" keyword starts the document ...
234 views

### Why are heuristics a disadvantage for decidable problems?

I'm reading Introduction to Artificial Intelligence by Ertel. This line has me stumped from the textbook (page 102): For decidable problems such as the 8-puzzle this means that the whole search ...
1k views

### Most efficient way to generate all descendents of all nodes in a tree

I'm looking for the most efficient algorithm to take a tree (stored as either a list of edges; OR as a list of mappings from parent node to a list of child nodes); and produce, for EVERY node, a list ...