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.
87
questions with no upvoted or accepted answers
7
votes
0
answers
528
views
Red-black tree appears to be slower than std::multimap
I've written a red-black tree in C as an exercise. The tree works and it is not bad, but it is about 10% slower than std::multimap from libstdc++ which I'm ...
- 1,342
6
votes
0
answers
467
views
C - fully threaded binary search trees
For learning purposes, I've decided to implement several classic data structures, starting with binary search trees. The entire code can be seen here, in a frozen branch ...
- 449
5
votes
0
answers
717
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 (...
5
votes
0
answers
49
views
Macao, a General Game Playing AI library - Game state goes in, best move comes out
I'm working on a simple General Game Playing AI library. The idea is that it should work with almost any kind of game, with a minimum of configuration. At the moment, I have it working on 2 player ...
- 265
5
votes
0
answers
1k
views
B+ Tree Visualization in LaTeX/TikZ
I have written a LaTeX package to visualize B+ trees.
The main purpose is to provide a simple but powerful package which provides a convenient interface.
However, this is my first LaTeX package and ...
- 59
5
votes
0
answers
439
views
Persistent segment tree
I'm trying to solve this problem.
Given a sequence \$B=B_0,B_1,\ldots,B_{N−1}\$
for each query \$(P,K)\$, find the minimum \$S\$
s.t. there are at least \$K\$ entries in \$B\$ that satisfies
...
- 358
5
votes
0
answers
247
views
Equivalent binary trees (structure & values)
I am following the Golang tour and I have been asked to build a couple of functions to manipulate binary trees.
My code runs as expected, but I would like to know if I could further improve my code. ...
- 317
4
votes
0
answers
331
views
JavaScript AVL Tree
I have been working through Introduction to Algorithms 3rd Edition, and have implemented an AVL tree through prototypal inheritance. The code presented here does work as expected based on the tests ...
- 1,245
4
votes
0
answers
127
views
All the paths from the root to the leaves
Given a binary tree, return all root-to-leaf paths.
Example:
-- 1
/ \
2 3
\
5
Output should be: ["1->2->5", "1->3"]
My approach: I walk the branches ...
- 596
4
votes
0
answers
3k
views
Compression/decompression using Huffman Coding Algorithm
I am writing a program that compresses and decompresses data using the Huffman Coding algorithm.
About compression: this program will export 2 files: header file (contains characters' frequency for ...
- 41
4
votes
0
answers
1k
views
Implementation of binary search tree
I require a code review in terms of correctness, style consistency, efficiency, code readability, and "pythonic"ness.
...
4
votes
0
answers
5k
views
Building a tree structure from pairs of parent-child to retrieve all ancestors of a leaf
I am trying to build a tree similar to this one :
1
/ \
2 3
/|\
4 5 6
/
7
With that tree, I must be able to get all ancestors for each ...
- 313
4
votes
0
answers
110
views
Heterogenous tree in the application domain: How do I represent them?
The Domain
I have three types of items in my domain: ItemA, ItemB, ItemC. (I can't use their real names.) ItemA has one attribute: thing_id. ItemB has 6 attributes: thing_id, name, description, ...
- 1,115
3
votes
0
answers
258
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 ...
3
votes
0
answers
292
views
reverse recursive search on an object with javascript - like tree search
I implemented a tree search with JavaScript.
It has below basic rules.
It will search over an array of objects which has recursive(like fractal)
If it found a according data in a leaf(the final ...
- 321
3
votes
0
answers
1k
views
AVL Tree with delete method in Python 3
Just a general code review. I'm looking for my first developer job so anything constructive is awesome. Please, and thank you very much.
I've written this implementation as an exercise and to add to ...
- 373
3
votes
0
answers
88
views
Binary Search Tree in Python 3
I just implemented binary search tree as described in Cormen's algorithm book. I'm not interested in correctness or performance of the implementation. I'm looking for reviews, comments on code style ...
- 139
3
votes
0
answers
1k
views
Red-black tree in Rust
Although I have done a few toy projects in Rust, I haven't really done anything related to tedious memory management tasks. So I set out to create a database with the help of the project 500 lines or ...
- 143
3
votes
0
answers
673
views
Building a k-d tree in Python
To learn Python, I have implemented a function that creates a k-d tree from a list of 2-d Points. I would like to refer to this question where i asked about the k-d tree in C. However, the Python code ...
- 213
3
votes
0
answers
120
views
Splay tree using shared and weak pointers
I'm having fun with shared pointers in a splay tree. Please let me know what I can do about code readability, and if you have any tips on speeding up my code, let know about that too (however, I am ...
- 141
3
votes
0
answers
128
views
FizzBuzz - A quartet of solutions
Since the FizzBuzz challenge is about developing ideas, I've added
a third test case for which I chose divisibility by 7 and its accompanying
tag "Go". This tag was purposely given a length other ...
- 4,278
3
votes
0
answers
78
views
Optimising insert operation for btree
I'm working on implementation insert operation for a btree, and would like to know if there is any way to optimise the inserting operation to make it go faster. The code seems really long so I'm ...
- 131
3
votes
0
answers
3k
views
In-memory B+ Tree in C++
I know B+ trees are not meant to be use in memory, but I just implemented it as an exercise. I'm looking for a general review.
...
- 2,954
3
votes
0
answers
54
views
LinkedList of Nodes at each level - optimalization
That's already known problem: to return an array of linked lists that contain values of elements at each level. Eg for tree with depth n there should be n linked lists.
I wrote the solution:
...
- 131
3
votes
0
answers
911
views
AVL Tree Implementation in Haskell
I'd like to get some feedback on my AVL tree implementation. I appreciate any comments related to style and performance, particularly if something can be written in a more concise or idiomatic way. If ...
- 581
3
votes
0
answers
2k
views
Data model for complex tree (multiple children and multiple parents)
I'd like to have a discussion on the data model (mostly) for a tree with nodes having multiple children and multiple parents.
I already have a working algorithm, but I'm looking for improvements.
The ...
- 303
3
votes
0
answers
253
views
Zipper trees implementation
Considering the lack of general purpose library to manipulate trees (not to mention zipper ones), I may end up packaging this piece of code, so I would like it to be reviewed first.
Any comment is ...
- 141
3
votes
0
answers
4k
views
Print all possible sequences that could have created this BST
I was working through Cracking The Coding interview, and I couldn't wrap my brain around their solution to one of the problems, so I ended up coming up with my own that, IMHO, is a lot cleaner and ...
- 455
3
votes
0
answers
292
views
Print the nodes of binary tree column-wise, using recursion and iteration
I am trying to code for both recursive and iterative approach to a problem.
Below is a recursive code to print the nodes of binarytree column wise. Basically I have count of root as 0 and if I move ...
- 31
3
votes
0
answers
290
views
Kruskal's algorithm in Java - follow-up
The previous and initial iteration at Kruskal's algorithm in Java
Now what I did is remove the fields and let the actual Kruskal-routine create the required data structures in the local scope, ...
- 26.7k
3
votes
0
answers
67
views
Basic Binary Tree in Go
As an exercise I have written a basic binary tree implementation in Go.
Tree struct:
...
- 213
3
votes
0
answers
61
views
2 4 tree insert function
I'm after creating an insert function for a 2 4 tree in Haskell. I'm just wondering if this is the best way to implement it (especially when handling the Root4s), ...
- 31
3
votes
0
answers
532
views
BST remove implementation
As practise, I implemented a BST and also the remove() method, but I figured I always have to check if the node being deleted is coming from the left child or the ...
- 31
2
votes
1
answer
185
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 ...
- 698
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 ...
- 1,835
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)
...
- 121
2
votes
0
answers
55
views
Linked tree built from (n) leaves
Firstly, here is the relevant code. It is written in kotlin.
...
2
votes
0
answers
87
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,204
2
votes
0
answers
42
views
Traversing a tree with two types of nodes, while keeping track of all ancestors
I wrote code that stores an AWS Organization tree in a tree data structure in Rust. From the tree, I use a slightly modified preorder traversal algorithm to print all of the accounts in the ...
- 121
2
votes
0
answers
294
views
Python multiprocessing for tasks depending on each other
I have a simulation that runs a process on a tree structure, where the slow processes down processes are separate from each other. This looked like a thing that would be a prime candidate for ...
- 201
2
votes
0
answers
190
views
CIS 194 - UPenn Haskell Course (2013) - Homework 4 - Tree Folding
I have been self studying the UPenn Haskell course, and I am unable to get feedback/grading on the assignments complete. This specific portion that I am having concerns with asks to write a function <...
2
votes
0
answers
408
views
BinaryTree traversed in postorder (DFS), iteratively
I was given this coding question for a technical interview:
Given a binary tree, implement a method to populate the list
post_ordered_list with the data of the nodes traversed in postorder,
...
- 2,469
2
votes
0
answers
556
views
Python AVL Implementation
I wanted to get an understanding of different data structures and therefore implemented an AVL tree in Python. I hope that some of you might be willing to check it for correctness.
The binary tree ...
- 21
2
votes
0
answers
33
views
Public function that traverses through a tree
So I have this function that lets one traverse through a tree without having to get the root node of the tree. The user basically sends a parameter that is either ...
2
votes
0
answers
354
views
Follow-up 1: Compare 2 unordered, rooted trees for shape-isomorphism
The previous post can be found here.
In the previous post I tried to solve an exercise but found through the answer of Peilonrayz a bug in the code and 2 more while fixing it. These have now been ...
- 505
2
votes
0
answers
604
views
Vertical sum in a given binary tree
I'm working on this problem,
Problem statement,
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines.
Examples:
...
- 3,443
2
votes
0
answers
341
views
GSS4 - Segment Tree implementation 2
The problem is also known as GSS4. The exact detail can be seen here but I reached TLE.
You are given a sequence A of N(N <= 100,000) positive integers. There
sum will be less than \$10^{18}\$....
- 141
2
votes
0
answers
368
views
Simple Unbalanced KDTree with 1NN Implementation
This is our first attempt at building an unbalanced k-dimensional tree with nearest neighbor (1NN) lookup to process multi-dimensional data. In particular, the "suspect region" in the ...
- 533
2
votes
0
answers
2k
views
HashMap with binary search tree for chaining
My friend was asked to implement a hashtable with a binary search tree. I tried practicing it myself, and it turned out to be very verbose. I need suggestions to clean this up!
...
- 341
2
votes
0
answers
141
views
In-memory B-Tree
I know B-Trees are meant to be used for external memory, but I implement it to understand the algorithms involved in insertion and deletion. Also, I didn't use a vector because I was asked not to use ...
- 2,954