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.

94 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
12
votes
0answers
492 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 ...
8
votes
0answers
296 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 ...
6
votes
0answers
291 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 ...
5
votes
0answers
29 views

Unbalanced search tree for comparing multiple string arrays

I have a system that stores resources. A resource contains a string that represents a user role, for example "3". With this user role "3", you can retrieve a list of permissions for the user role, ...
5
votes
0answers
38 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 ...
5
votes
0answers
913 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 ...
5
votes
0answers
404 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 ...
5
votes
0answers
200 views

Trinary Search Tree

I'm probably not the first to think this up, but here we go. An trinary search tree is a generalization of a binary search tree in the sense that instead of a comparison function returning true or ...
5
votes
0answers
368 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 ...
4
votes
0answers
57 views

Ternary Search Tree / N-Gram Model in Python

I implemented a word n-gram model using a character ternary search tree. It is intended to be passed a generator that yields a long sequence of words (from a corpus) and its requirements are that it ...
4
votes
0answers
2k 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 ...
4
votes
0answers
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
2answers
2k views

Loop for inserting a node into a binary search tree

I am trying to implement binary search tree. One method which I am trying to implement in the most efficient and stylish way is node insertion. I am under the impression that while (true) is a bad ...
4
votes
1answer
852 views

Turning a 2D array into a tree

I have the following data structure that's obtained from a third party: ...
4
votes
0answers
3k 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 ...
4
votes
0answers
233 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. ...
3
votes
0answers
36 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 ...
3
votes
1answer
43 views

Adding an item to a hierarchical data structure

What I need to do is create a new object, modify it using a recursive function, then merge it with another object, and do this all in such a way that the values of the new object take precedence over ...
3
votes
0answers
92 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 ...
3
votes
0answers
70 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 ...
3
votes
0answers
391 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 ...
3
votes
0answers
348 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 ...
3
votes
0answers
108 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 ...
3
votes
0answers
83 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 ...
3
votes
0answers
73 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 ...
3
votes
0answers
2k 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. ...
3
votes
0answers
493 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 ...
3
votes
0answers
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 ...
3
votes
0answers
222 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 ...
3
votes
0answers
263 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 ...
3
votes
0answers
54 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), ...
3
votes
0answers
516 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 ...
3
votes
0answers
106 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, ...
2
votes
0answers
20 views

Implementation of Generic Binary Tree Code

I'm in the process of independently learning Generics as a way to build on a college assignment for Binary Search Tree. I've completed this program without Generics first and now I've converted over ...
2
votes
0answers
235 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 ...
2
votes
0answers
61 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 ...
2
votes
0answers
127 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
0answers
303 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
votes
0answers
31 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
0answers
237 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 ...
2
votes
0answers
420 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: ...
2
votes
0answers
234 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}\$....
2
votes
0answers
248 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 ...
2
votes
0answers
1k 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! ...
2
votes
0answers
48 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: ...
2
votes
0answers
120 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
votes
0answers
718 views

An AVL-tree based order statistic tree in Java

I have this java.util.Set implementation that is based on AVL-trees, which implies that the set is sorted. However, it provides two additional operations: ...
2
votes
0answers
102 views

Coloring trees in Elixir

The following is my tree coloring realisation attempted to get a feel of Elixir (simple, but slow coloring algorithm from Principles of Distributed Computing). Coloring runs from the root, using ...
2
votes
0answers
3k 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 ...
2
votes
0answers
436 views

Efficient Sets and Maps with Treaps

I wrote up a Treap implementation to serve as the base class for a bunch of augmented data structures (interval sets, plane (2D) sets, order statistic trees), replacing my RB-tree base. Some ...