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.
888
questions
0
votes
0
answers
48
views
Python Binary Search Tree Simplification [closed]
I am looking to get some feedback on the following code. In particular, I am wondering what can be improved in this implementation and whether there are any errors. I am also wondering if there is a ...
- 479
2
votes
1
answer
108
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 ...
- 123
4
votes
3
answers
108
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 ...
- 1,643
1
vote
1
answer
62
views
Is there a better way to traverse a list of tree nodes efficiently
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 ...
- 688
1
vote
1
answer
69
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 ...
- 26.1k
1
vote
1
answer
53
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
...
- 269
2
votes
2
answers
41
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+...
- 21
1
vote
1
answer
70
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 ...
- 222
1
vote
0
answers
120
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,596
2
votes
0
answers
85
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 ...
- 1,835
1
vote
1
answer
52
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.
...
- 26.1k
0
votes
0
answers
39
views
General (multiple nodes) LCA queries in Java
I have an algorithm for computing multiple node LCAs (lowest common ancestor):
TreeNode.java:
...
- 26.1k
0
votes
1
answer
89
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 ...
- 11
3
votes
1
answer
160
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 ...
- 31
1
vote
1
answer
128
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:
...
- 26.1k
-1
votes
1
answer
101
views
Finding the 10 most frequent words from a given file ( huge amount of words) but there are stop words [closed]
I'm using Trie and MinHeap while writing my code but I stuck at one point. While counting the most frequent words I should not count the stop words and there is a file called stopwords.txt. Somehow I ...
- 1
4
votes
0
answers
298
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 (...
2
votes
1
answer
75
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 ...
-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/...
0
votes
1
answer
138
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 ...
2
votes
1
answer
71
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 ...
- 21
1
vote
1
answer
423
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):
...
- 129
3
votes
1
answer
71
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 ...
- 133
3
votes
1
answer
70
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 ...
- 403
2
votes
1
answer
117
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)
...
- 121
2
votes
1
answer
75
views
Haskell Dynamic Programming on a Tree
Here is my shot at Homework 8 of CIS-194 (from Spring '13). The problem is about a hierarchy of employees at a company (a tree), each node being of type Employee, ...
- 125
2
votes
1
answer
59
views
Pretty print a tree from minimal data input
I'm currently working on an uncrafting tool for minecraft and got a neat output working that shows all the materials needed in a tree. I wonder if the code used to print that tree could be improved ...
- 846
2
votes
1
answer
139
views
Implementation of binary tree traversal
Based on what i understood of Binary Tree, queue and recursion I implemented this Breadth First Search algorithm as follows.
Do you have any suggestions to improve (in term of readability, good ...
- 273
2
votes
2
answers
58
views
Code structure for tree representation with multiple types (classes) of nodes and circular dependencies
I am developing a piece of code around a tree structure. The tree can do a few things - one of them being its ability to serialize & de-serialize its data. There are multiple different types of ...
- 273
1
vote
0
answers
29
views
Set operations on a tree / Hierarchical set class
Initially, I posted this question on StackOverflow. I wanted to know if there's an existing library that implements the concept I have in mind, which is the following.
I want to define a hierarchy/...
- 369
3
votes
1
answer
39
views
Counting unival subtrees - Follow Up
This code is a revised version of the implementation which asked for an advice on improvement. Original post here: Counting unival subtrees
Credits to: [Deduplicator], [Reinderien], [Toby Speight], [...
5
votes
1
answer
178
views
Implementing an autocomplete system
Question:
Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix.
For example, given the query ...
2
votes
2
answers
99
views
Lowest Common Ancestor in Binary Tree (Iterative)
In the below code I've implemented a method to find the lowest common ancestor of a binary tree.
This is an iterative approach using this pseudocode.
Please suggest any improvements that can be made.
<...
- 433
4
votes
1
answer
72
views
A Concurrent Tree implementation with consistent snapshot capability
I have a tree in my application from which I need to periodically take a snapshot. I've been using locks so far, but after running into a few deadlock issues I decided to create a lock-free ...
- 417
4
votes
4
answers
1k
views
Check if a binary tree is symmetric in Python
I have solved the following Leetcode problem.
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric....
- 169
9
votes
1
answer
274
views
Construction and search of Kd-Tree in c++
I am not very fluent in C++ and want to construct a Kd-Tree in C++ based on this paper Efficient Locally Weighted Polynomial Regression Predictions, to use it to conduct some fast implementations of ...
2
votes
1
answer
95
views
HackerRank - Binary tree to compute the Nth power of natural numbers that sum up to X
I'm trying to solve this challenge on HackerRank.
In short, given x and n, I have to determine how many ways I can pick numbers ...
- 507
9
votes
1
answer
738
views
Using smart pointers to construct Binary Search Tree
I have three main questions:
Am I using std::unique_ptr correctly here? Using std::move and ...
- 375
6
votes
1
answer
472
views
C++ : Red-Black Tree with std::unique_ptr
This is my C++ implementation of a Red-Black Tree, referring the CLRS book.
Half for fun, half for studying.
As implementing child node, I chose std::unique_ptr ...
- 1,643
2
votes
0
answers
38
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 ...
- 121
2
votes
0
answers
55
views
Linked tree built from (n) leaves
Firstly, here is the relevant code. It is written in kotlin.
...
8
votes
1
answer
1k
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.
<...
user227128
3
votes
1
answer
50
views
XML Tree Reformatter requested code. C#
So this is a post as per request in a different post on stack overflow: https://stackoverflow.com/questions/62412713/why-does-my-c-sharp-xml-code-only-work-when-i-enumerate-variable-enumerable. The ...
- 31
2
votes
1
answer
255
views
Sum of all Paths in Binary Tree
Problem
For the given binary tree return the list which has sum of every paths in a tree. i.e Every path from root to leaf.
I've written following solution.
...
- 309
3
votes
0
answers
200
views
Noughts and Crosses Terminal Game with AI
I created a game which can play tic-tac-toe with: 0 players (AI vs AI), 1 player (human vs AI) or 2 player (human vs human).
Here is the AI function which wraps around my innermost function. This ...
4
votes
1
answer
99
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?
...
- 1,180
2
votes
0
answers
84
views
Max Heap Implementation in Python
I decided to challenge myself to code this data structure by just seeing how it looks visually and this is what I got. I can change this easily to minheap by changing some greater than (>) operators. ...
- 1,180
1
vote
2
answers
150
views
Leetcode: Cousins in Binary Tree
Mu solution to Leetcode problem Cousins in Binary Tree works, but the code feels bulky. Is there a better way to solve this problem, particularly to use less additional variables? I will appreciate ...
- 313
1
vote
1
answer
96
views
Data mining in Java: finding undrawn lottery rows - follow-up
(See the previous (initial) iteration.)
This time, I have substantially reduced the usage of the final and this keywords. Also, ...
- 26.1k
2
votes
2
answers
114
views
Data mining in Java: finding undrawn lottery rows
(See the next iteration.)
Introduction
Suppose Evil Lottery Inc is interested in not paying millions of dollars back to players. They gather the drawn lottery rows first, after which they mine rows ...
- 26.1k