Questions tagged [tree]
A tree is a graph in which there is exactly one path between any two nodes. It is often used as a hierarchical data structure.
889
questions
2
votes
1
answer
141
views
Monte Carlo Tree Search Optimization and Loss Prevention
I'm working on an implementation of Monte Carlo Tree Search in Swift.
It's not bad, but it could be better! I'm principally interested in making my algorithm:
faster (more iterations/second)
...
CommunityBot
- 1
2
votes
1
answer
63
views
QuadTree implementation in c++
I'm new on C++ and OOP. I wrote the following QuadTree implementation (I didn't wrote the remove object part yet).
please take a look on it and provide feedback, mainly about C++ OOP design, ...
- 44.8k
2
votes
1
answer
186
views
Traverse a list of tree nodes
I am wondering if there is a better way to traverse a list of trees.
Here is my current algorithm:
Collect the parent IDs in a Map
Traverse all the groups and find ones where their ID is not in the ...
CommunityBot
- 1
5
votes
1
answer
312
views
Port Node and TreeBuilder from Python to C++
I am trying to port a TreeBuilder Python class to C++, keeping the structure as close as possible to the original. Here is a simplified Python version: https://onlinegdb.com/I4dg0hCtg
The purpose of ...
- 408
2
votes
1
answer
91
views
Find Invalid User Relationships in User to Manager Map (validate map as valid tree structure with no circular relationships)
We have a new service where an admin can upload a spreadsheet of new users they want to add to our application. During our processing we make a union map of all the users both existing and new ...
- 68.9k
4
votes
2
answers
418
views
Leet Code: 236. Lowest Common Ancestor of a Binary Tree
Trying my hand at Leet 236.
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is ...
- 68.9k
3
votes
3
answers
282
views
Leet Code: 236. Lowest Common Ancestor of a Binary Tree. First version
Trying my hand at Leet 236
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is ...
- 44.8k
0
votes
0
answers
50
views
Traversing a 2D array with a tree
In order to help me solve the December Jane Street puzzle "Die Agony" I wrote a quick and dirty script to manually brute-force through the thing and do the calculations for me.
I then tried ...
- 231
3
votes
1
answer
352
views
Converting String to Binary Hash Tree
I've written a pretty basic algorithm to convert a string to a binary hash tree of its characters, where each character represents a leaf node. The hash tree itself is being stored in a vector.
If the ...
- 44.8k
3
votes
2
answers
228
views
Implementation of a market that matches bids to offers
This is my task:
Each line in the file can be one of the following:
Updates to the limit order book in the following format:
...
- 68.9k
0
votes
0
answers
34
views
Java pathfinding in general trees - Part 2/4: algorithms
Java pathfinding in general trees - Part 1/4: model classes
Java pathfinding in general trees - Part 2/4: algorithms (this post)
Java pathfinding in general trees - Part 3/4: demonstration
Java ...
- 26.7k
0
votes
0
answers
57
views
Java pathfinding in general trees - Part 1/4: model classes
Java pathfinding in general trees - Part 1/4: model classes (this post)
Java pathfinding in general trees - Part 2/4: algorithms
Java pathfinding in general trees - Part 3/4: demonstration
Java ...
- 26.7k
4
votes
2
answers
122
views
Extract indices of visible nodes in a tree where only some nodes are expanded
A program that I work on constantly updates and modifies program state containing an arbitrarily deep and wide tree. The data looks something like this.
...
- 585
4
votes
2
answers
4k
views
Build a flat List from a Tree structure in Java
I have a Tree structure represented by a List, which I want to get it flattened.
I wrote the function below:
...
- 1
2
votes
2
answers
28k
views
A binary tree , its copy constructor and assignment operator
I implemented a binary tree in the following code. Its node's copy constructor and assignment operator should copy itself and all its descendents. Similarity a node's destructor should delete itself ...
- 68.9k
4
votes
3
answers
158
views
C++ B-Tree serialization/deserialization
Yesterday I wrote a serialization/deserialization for my B-Tree library.
Since the code for whole tree is too large to upload here, I'll upload only serialization/deserialization and node class ...
- 143k
6
votes
1
answer
527
views
Specialty tree structure - BK Tree
I've been working on a implementation of specialty tree structure called a BK-Tree (more here and here). Basically, it's a tree that allows relatively efficient querying for items within a specific ...
- 68.9k
2
votes
1
answer
117
views
function to group data by parent branches
I wrote this function to take database output like from PDO's fetchAll(PDO::FETCH_ASSOC) and turn it into a tree. For small datasets it works well. However, when ...
- 26.6k
1
vote
1
answer
74
views
Java - Select the maximum integers from sliding windows over an array
So I have the following algorithm. Given an array A[0 ... n - 1] and the window length w, compute all the windows ...
- 5,499
5
votes
1
answer
7k
views
Construct the tree from a list of edges
I was using the following code to construct the tree from a list of nodes: [1, 2] means that there is a bi-directional link between ...
1
vote
1
answer
101
views
Binary Search Tree implementation in C++ with templates
Im implementing a BST using templates and dynamic memory, here is my attempt:
This is the BSTNode.hh
...
- 44.8k
2
votes
2
answers
49
views
Simple non balancing indexed binary search tree
The following code represents a simple indexed binary search tree of integers. The insert method inserts an int. The indexed lookup looks up the ith smallest element (0 indexed). I'm trying to write C+...
- 143k
1
vote
0
answers
978
views
Replacing multiple substrings in C#
There is a String.Replace method in C# and it is 1-1 mapping replacing operation, i.e. single Unicode character / string source replaced with another single Unicode ...
- 3,830
1
vote
1
answer
81
views
Decision Tree for classification tasks in Python
I've decided to implement the ID3 Decision Tree algorithm in Python based on what I've learned from George F. Luger's textbook on AI (and other secondary readings). As far as I know, the code is ...
- 56k
1
vote
2
answers
429
views
Leetcode - find if BST is valid or not
Given a binary tree, determine if it is a valid binary search tree
(BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the
node'...
- 1,497
1
vote
2
answers
666
views
Binary tree pruning with BFS
Below the text of the exercise:
We are given the head node root of a binary tree, where additionally
every node's value is either a 0 or a 1.
Return the same tree where every subtree (of the ...
- 143k
2
votes
0
answers
187
views
Simple Merkle Tree
Discussion
I just started learning about Merkle Trees and wanted to get some practice by attempting to implement a very simple Merkle Tree.
The constructor for the tree takes some type of hash ...
- 143k
1
vote
1
answer
60
views
Comparing two general LCA algorithms in Java
Now I have two algorithms solving a problem: given a general (multi-way) tree, and any array of node names, find the the node that is the deepest common ancestor.
...
- 5,499
0
votes
1
answer
241
views
Populate TreeView with arbitrary depth from DataTable
I have a DataTable with id, parent, label columns and want to populate a TreeView with it.
I'm new to c# and as far as I understand, there is no ready solution for it, unlike some other languages.
So ...
- 8,024
0
votes
1
answer
177
views
Leetcode 662. Maximum Width of Binary Tree Javascript FlatMap attempt - Time Limit Exceeded
Problem Statement:
Given the root of a binary tree, return the maximum width of the given
tree.
The maximum width of a tree is the maximum width among all levels.
The width of one level is defined as ...
- 68.9k
1
vote
2
answers
646
views
Recursive way to find inorder successor
So far I have attempted to find the inorder successor through recursion and it seems to be working right. Can someone review the code and give suggestions?
...
- 68.9k
3
votes
1
answer
278
views
Barnes-Hut \$n\$-body simulation (3D) in C++
I have implemented the Barnes-Hut algorithm for \$n\$-body-simulations (in this case "sort-of" 3D-gravity - see below). I'd appreciate any comments for improving my code (especially ...
- 44.8k
16
votes
3
answers
7k
views
The median of the given AVL tree
A long time ago I found this question and asked about an algorithm here.
My code is also available on GitHub.
Given a self-balancing tree (AVL), code a method that returns the
median.
(...
- 68.9k
1
vote
1
answer
174
views
Comparing a prefix tree against a HashSet of strings in Java
Here, I have made an attempt to find out whether a prefix tree is any more efficient than a simple java.util.HashSet<String>. See what I have:
...
- 6,383
5
votes
4
answers
5k
views
Path sum in binary tree
Root to leaf path sum equal to a given number
Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given ...
- 3,336
5
votes
0
answers
719
views
Tree for PowerShell
This Module started as a fun coding exercise designed to emulate the tree command and also calculate the size of each folder based of the files size of that folder (...
4
votes
2
answers
13k
views
Java: Given a list of edges, build a tree and return the root
In an interview I was asked to write Java code to build a tree and return the root, given a list of edges. It was a fairly open ended question where the interviewer left all the decisions up to me.
I ...
- 1
2
votes
1
answer
116
views
A Lowest Common Ancestor (LCA) Tree Algorithm
My implementation of the lowest common ancestor (LCA) algorithm for my tree data structure. I selected the non-preprocessed (naïve) implementation for this first implementation. Support for any number ...
- 44.8k
4
votes
1
answer
122
views
AVL Tree implementation Based on VisualGo
I have tried implementing an AVL Tree on my own, based on visualising it. But i'm unsure how many testcases it work with, and how efficient it is. Are there any ways to make it efficient, and compact?
...
CommunityBot
- 1
-1
votes
1
answer
48
views
is my Prim's MST implementation terse enough?
I did research because I want to learn Kruskal's and Prim's MSTs. I did research and after a solid understanding, I went to my textbook and got their libraries:
https://algs4.cs.princeton.edu/code/...
- 5,499
1
vote
0
answers
300
views
Binary Search Tree find_successor of inputNode
Wanted to ask for feedback for my coding challenge for BST. python find_successor of inputNode inOrder.
https://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/
find the successor(...
- 42.3k
1
vote
1
answer
4k
views
Binary search tree implementation in Python
I am reading about algorithms and got to the binary search trees. I wanted to ask if the following implementation of a Binary Tree is correct.
...
- 5,499
8
votes
1
answer
2k
views
Red-Black Tree Implementation in Python
I'm wondering if there are better practices, and optimizations I could make on my code, to do things easier/faster.
I have added comments, in many places in the code, to make understanding easier.
<...
- 5,499
9
votes
3
answers
8k
views
Implementing a binary tree in C++ using "std::unique_ptr"
I have implemented a simple binary search tree class in C++ using std::unique_ptr objects to hold the pointers to each node. In doing this I have come across a ...
- 68.9k
2
votes
1
answer
108
views
Find ALL duplicate subtrees. using recursion
This is just a practice exercise, I'm trying to understand dynamic programming as deeply as I can. I solved this using recursion, though I am not sure if it will always work. If anyone could tell me a ...
- 1,915
2
votes
2
answers
4k
views
Dictionary operations on a Binary Search Tree data structure?
today I tried to code all the dictionary operations such as Search, Successor, Predecessor, Minimum, Maximum, Insert, Delete etc. for a Binary Search Tree data structure using the Java programming ...
1
vote
1
answer
788
views
How does one write DFS in python with a Deque without reversed for Trees?
I have implemented a correct version of DFS (with comments explaining the implementation):
...
- 42.3k
15
votes
1
answer
662
views
Binary Search Tree Monad Implementation
I've written a Binary Search Tree Monad in Scala. I would like to hear your thoughts on how to improve it (e.g. making insertion/deletion/search faster and more scalable). Also, is there a better way ...
CommunityBot
- 1
3
votes
1
answer
88
views
Building a tree containing all permutations of arithmetic expressions given some numbers
Given any series of numbers, for example 1,2,3,4,5 and given the arithmetic operands + - * / including parenthesis, what would be the most optimal way to build a tree that contains all permutations ...
- 6,383
3
votes
1
answer
91
views
AVL Tree in C Criticism
I have made an AVL tree in C and coded the basic functionality of insertion, deletion, and search. I would love some criticism on my implementation especially on the insertion and deletion section of ...
- 28.1k