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.
93
questions
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
10
votes
1
answer
5k
views
Binary trees in Rust: iterators
This is a follow-up to Basic binary tree manipulation in Rust, where Shepmaster suggested that I implement the Iterator trait for the binary tree.
This ended up ...
- 1,169
10
votes
2
answers
2k
views
Generic binary search tree in C++
Introduction
This is yet another data structure I'm going over again for the algorithms course. This time it is binary search tree.
Implemented operations:
Insert
Exists
Remove
Clear
Move ...
- 9,259
8
votes
3
answers
1k
views
Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree
Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree.
Given tree:
...
- 8,391
8
votes
1
answer
742
views
Are AVL trees equal?
I was inspired by this answer and decided to implement an AVL tree with the methods equals and hashCode as if I was asked to do ...
- 1,355
6
votes
2
answers
546
views
Improved Van Emde Boas tree based map in Java
After working on Van Emde Boas tree -based map in Java, I came up with this code. I managed to fix the bugs and improve the performance by using internally primitive integers instead of wrapped ...
- 26.7k
6
votes
3
answers
4k
views
Building tree structure based on flat objects
You can find here a Follow-up question
Description
A List<UnrelatedObects> is returned by a 3rd party webservice, which will then be transformed to a ...
- 50.1k
6
votes
3
answers
2k
views
Missing level of technical depth (Flatten Tree)
I recently have given a coding test in a reputable IT company. There were three coding questions.
They refused me by saying that
as we felt they didn't demonstrate the level of technical depth we'...
- 409
6
votes
2
answers
10k
views
Kruskal's algorithm in Java
I have this Java implementation of Kruskal's algorithm. It solves a tiny problem instance correctly, yet I am not quite sure, whether my implementation is correct.
The code as follows:
MSTFinder....
- 26.7k
6
votes
1
answer
54
views
Searching a Join List for an index Attempt #2
Originally I posted this incorrect attempt - Searching a Join List for an index.
Given a JoinList:
...
- 3,183
5
votes
1
answer
82
views
Retrieve annotation from a tree annotated with a Monoid
Working on this homework from 2013 for self-learning.
For the following Algebraic Data Type:
...
- 3,183
4
votes
1
answer
492
views
Using range minimal query for lowest common ancestor (LCA)
Here is my code to use range minimal query to resolve the LCA problem. Any advice on code bugs, performance improvement in terms of algorithm time complexity, code style are appreciated.
More ...
- 3,443
4
votes
3
answers
3k
views
(Re)Creating a tree from a flat collection (or "unflatten" a tree)
I need to create a tree from a flat collection. The order of elements is defined in a specification so it's rather impossible that it will ever change... but I want the whole algorithm to be ...
- 44k
3
votes
2
answers
660
views
Building tree structure based on flat objects - follow up
This is a follow up on this question and has now a follow up question here.
I have implemented some changes to the class below and also added the method ...
- 50.1k
2
votes
4
answers
3k
views
Detect if a tree is complete binary tree
Detect if tree is complete binary tree. This question is improvement over previously asked here. Looking for code-review, optimizations and best practices.
Verifying both space and time complexity to ...
- 8,391
0
votes
1
answer
101
views
Follow-up zp-Tree to represent Trees as nested arrays
This is a follow-up on my previous post.
I have made modifications based on the feedback received on the previous post, hence I request another review on the modified code if ok.
Note: review ...
- 159
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.
(...
- 1,355
15
votes
1
answer
10k
views
Printing a Binary Tree top-down (column wise)
We have a binary tree, suppose like this:
8
/ \
6 10
/ \ / \
4 7 9 12
/ \
3 5
We have to print this binary tree in top-down ...
- 680
15
votes
4
answers
8k
views
Google Foobar Challenge: Lucky Triples
Note: Since my time has passed for this challenge, I do not remember exactly the stipulations but will attempt to recapitulate them to the best of my knowledge.
Essentially, the challenge was this:
...
- 153
12
votes
4
answers
6k
views
Extraction of value from a dict-tree, given a path of arbitrary length
Problem: We read a complex json-file which grants us a tree in terms of a python "dict of dicts". We're then requested to retrieve a specific path from the tree, represented by a list of elements. The ...
- 223
11
votes
4
answers
3k
views
Composite and Visitor patterns for tree-based survey functionality in C#
I have written some survey functionality for a project. Basically, a generic survey form that can be composed of sections and questions.
I have a Survey class, <...
- 211
10
votes
1
answer
958
views
BFS and DFS tree traversal
I posted some code as part of an answer to another question and I thought it would be a good idea to get that code reviewed also.
Any comments are welcomed, but I am mostly annoyed by ...
- 5,390
10
votes
2
answers
176
views
Trees and their uses
I was getting sicker and sicker of using an ordinary collection to do a tree's work, so I built a tree. A requirement of the tree are that it needs to contain a key to sort the tree by, so I used a <...
user34073
9
votes
1
answer
872
views
Prefix trees for auto suggest
I wrote a quick prefix tree implementation. I know it may be far from perfect, but I need to make sure that I got the basics right.
My main concerns are:
Have I settled for the correct data ...
- 193
8
votes
2
answers
3k
views
Barnes-Hut n-body quadtree
Here's an attempt I've made of implementing the Barnes-Hut n-body algorithm, or its initial stage - The quadtree. That there're lots of lengthy doc strings might excuse the lack of detailed ...
- 455
8
votes
4
answers
7k
views
Basic Postfix Calculator in Java
I recently posted some sample code that I was providing students with and got great feedback so figured I post another one of the examples I will be providing students with. (See Simple Example of an ...
- 782
7
votes
2
answers
2k
views
Generic in order traversal iterator for binary trees
This actually started off as member type for the binary_search_tree, but after realizing that it doesn't compare to values or use the value objects inside of it, I ...
- 9,259
7
votes
1
answer
967
views
Binary trees in Rust: more iterators! (non-consuming variant)
This is a follow-up to Binary trees in Rust: iterators, where Shepmaster suggested that I implement a non-consuming iterator.
This was relatively straightforward.
I chose to mirror the design of the ...
- 1,169
7
votes
1
answer
3k
views
Trie Tree match string containing ? and *
Using Python 2.7 and here is my code which implement trie match for a whole word, and also support if the whole word contains ? (match any one character) or ...
- 3,443
7
votes
2
answers
10k
views
Returning a list of the values from the binary tree
I want to return a list of the values from the binary tree. Is there a shorter and more efficient way to write the method for numbers?
...
- 171
7
votes
2
answers
761
views
Determine quadrant of code
I'm currently in the process of coding a QuadTree. The QuadTree seperates into four quadrants, with 1 being the top right and 4 being the bottom right. I have this code to determine which quadrant ...
- 357
6
votes
1
answer
669
views
Unbalanced binary search tree
I wrote this unbalanced binary tree and would like to know how to improve the code and performance. If you can point out any situations that are not being handled appropriately, that would be great ...
- 1,979
6
votes
3
answers
212
views
Tree abstraction
This code provides a Tree abstraction.
I would like to finalize the code structure only in tree directory, before starting ...
- 3,321
6
votes
5
answers
11k
views
DFS in Binary Tree
I have written this code for DFS in a binary tree and would like improvements on it.
...
- 449
6
votes
3
answers
7k
views
Tree structure with support for inorder and preorder traversal
I am learning Tree Data Structures and came up with this code for implementing basic Tree Node using class and performing various Tree based operations like Traversals and others. The code works ...
- 461
6
votes
3
answers
4k
views
Recursive binary search tree
How is my usage of std::unique_ptr() and std::move()? How can I improve this code?
...
- 2,718
6
votes
1
answer
90
views
BST with node count
I took a simple BST implementation which is only really a set (i.e. just element, not key value), and decided to add a node count. I was translating this, which is explained here.
In particular the ...
- 493
5
votes
1
answer
221
views
Using range minimal query for lowest common ancestor (LCA) -- part 2
Here is my code to use range minimal query to resolve the LCA problem. I applied comments from here.
Any advice on code bugs, performance improvement in terms of algorithm time complexity, code style ...
- 3,443
5
votes
0
answers
368
views
Van Emde Boas tree -based map in Java [duplicate]
(Follow-up question: Improved Van Emde Boas tree based map in Java)
For the experimental part of my MSc thesis I was working on van Emde Boas tree, and I have this:
...
- 26.7k
5
votes
1
answer
2k
views
Traversing the parent-child relationship between objects
I wrote this code because I was often annoyed that I couldn't get the parent object. This class allows you to traverse the parent-child relationship between objects, in both directions. It also ...
- 1,141
5
votes
1
answer
9k
views
Find height of a tree without using recursion
I want you to pick my code apart and give me some feedback on how I could make it better or simpler.
...
- 8,391
5
votes
2
answers
153
views
Leftist Tree in Dyalog APL -- can it be made more compact/idiomatic?
Following great feedback given in response to my previous question, I was encouraged to consider a different type of heap structure, the Leftist Tree. It lends itself better to a functional ...
- 195
5
votes
1
answer
1k
views
Basic binary tree manipulation in Rust
The goal here is to implement a basic binary tree with values only on leaves, with depth, mirror, and ...
- 1,169
5
votes
3
answers
2k
views
PrettyPrint a Binary Tree
I was going through this tutorial for Pretty Printing a binary search tree and decided to implement my own version. Here is my implementation. This version works only for trees that are complete ...
- 486
5
votes
1
answer
645
views
Josephus permutation
This problem is taken from the book Introduction to Algorithms, Third Edition
By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein:
We define the Josephus problem as ...
- 2,954
5
votes
2
answers
3k
views
BFS tree traversal Scala
I would love some feedback on the following code for BFS traversal in a binary tree. Is there a cleaner way to write this?
...
- 371
4
votes
3
answers
2k
views
Delete alternate nodes of a linked list
If the linked list is 1->2->3->4 then the output should be 1->3. If the linked list is 1->2->3->4->5, then the output should be 1->3->5.
The question is attributed to GeeksForGeeks. I'm looking for ...
- 8,391
4
votes
2
answers
2k
views
Memory management for Red-Black Tree
I've written this program yesterday, and I was reminded why I dreaded C++ before turning to Java: pointers and associated terms (like destructors, initializations and copy/move constructors) are ...
- 195
4
votes
2
answers
134
views
Building tree structure based on flat objects - second follow up
This is a follow up on this question which is a follow up on this question
This follow up is created, because the class in question contained something, which didn't do what it should do.
Based on ...
- 50.1k
4
votes
1
answer
6k
views
Immutable binary search tree using Scala
I have written a sample immutable binary search tree using Scala. However, I am not sure whether or not I was doing it the proper way since I am not an expert at functional programming. Is there a ...
user27521