Questions tagged [tree]
A tree is a widely-used data structure that emulates a hierarchical tree-like structure with a set of linked nodes.
16,781
questions
1598
votes
8
answers
338k
views
What are the options for storing hierarchical data in a relational database?
Good Overviews
Generally speaking, you're making a decision between fast read times (for example, nested set) or fast write times (adjacency list). Usually, you end up with a combination of the ...
577
votes
15
answers
141k
views
What is the most efficient/elegant way to parse a flat table into a tree?
Assume you have a flat table that stores an ordered tree hierarchy:
Id Name ParentId Order
1 'Node 1' 0 10
2 'Node 1.1' 1 10
3 'Node 2' 0 ...
- 335k
554
votes
6
answers
464k
views
Unable to show a Git tree in terminal
Killswitchcollective.com's old article, 30 June 2009, has the following inputs and outputs
git co master
git merge [your_branch]
git push
upstream A-B-C-D-E A-B-C-D-E-F-G
...
- 137k
553
votes
27
answers
835k
views
How to implement a tree data-structure in Java?
Is there any standard Java library class to represent a tree in Java?
Specifically I need to represent the following:
The sub-tree at any node can have an arbitrary number of children
Each node (...
- 5,549
442
votes
16
answers
269k
views
Why does the C++ STL not provide any "tree" containers?
Why does the C++ STL not provide any "tree" containers, and what's the best thing to use instead?
I want to store a hierarchy of objects as a tree, rather than use a tree as a performance enhancement....
- 67.4k
415
votes
13
answers
436k
views
What is the difference between depth and height in a tree?
This is a simple question from algorithms theory.
The difference between them is that in one case you count number of nodes and in other number of edges on the shortest path between root and concrete ...
- 18.4k
366
votes
14
answers
244k
views
Difference between binary tree and binary search tree
Can anyone please explain the difference between binary tree and binary search tree with an example?
- 10.1k
340
votes
20
answers
633k
views
How can I implement a tree in Python?
How can I implement a general tree in Python? Is there a built-in data structure for this?
- 4,065
268
votes
11
answers
210k
views
Google Chrome display JSON AJAX response as tree and not as a plain text
I cannot find an answer to this one:
My AJAX calls return JSON data. In Google Chrome Developer Tools > Resources > XHR when I click on the resource on the left and then on the Content tab I see ...
- 6,359
244
votes
3
answers
50k
views
What are the differences between segment trees, interval trees, binary indexed trees and range trees?
What are differences between segment trees, interval trees, binary indexed trees and range trees in terms of:
Key idea/definition
Applications
Performance/order in higher dimensions/space ...
- 5,559
225
votes
34
answers
281k
views
Build tree array from flat array in javascript
I have a complex json file that I have to handle with javascript to make it hierarchical, in order to later build a tree.
Every entry of the json has :
id : a unique id,
parentId : the id of the ...
- 2,489
213
votes
18
answers
153k
views
Non-recursive depth first search algorithm [closed]
I am looking for a non-recursive depth first search algorithm for a non-binary tree. Any help is very much appreciated.
- 11.7k
200
votes
22
answers
127k
views
How to build a tree from a flat structure?
I have a bunch of objects in a flat structure. These objects have an ID and a ParentID property so they can be arranged in trees. They are in no particular order.
Each ParentID property does not ...
- 5,940
194
votes
12
answers
125k
views
What's the difference between the data structure Tree and Graph?
Academically speaking, what's the essential difference between the data structure Tree and Graph? And how about the tree based search and Graph based search?
- 2,155
176
votes
5
answers
183k
views
Database Structure for Tree Data Structure [closed]
What would be the best way to implement a customizable tree data structure (meaning, a tree structure with an unknown number of level) in a database?
I've done this once before using a table with a ...
- 15.8k
140
votes
6
answers
361k
views
Tree view of a directory/folder in Windows? [closed]
In Linux/KDE, I can see a directory as a tree. How can I do it in Windows 7?
Consider I do NOT mean "Windows Explorer". This just shows the directories, I also want the files.
- 12.6k
135
votes
4
answers
62k
views
What is the difference between trie and radix trie data structures?
Are the trie and radix trie data structures the same thing?
If they aren't the same, then what is the meaning of radix trie (AKA Patricia trie)?
- 1,779
127
votes
7
answers
138k
views
Definition of a Balanced Tree
I am just wondering if someone might be able to clarify the definition of a balanced tree for me. I have that "a tree is balanced if each sub-tree is balanced and the height of the two sub-trees ...
- 1,431
118
votes
15
answers
63k
views
How to flatten tree via LINQ?
So I have simple tree:
class MyNode
{
public MyNode Parent;
public IEnumerable<MyNode> Elements;
int group = 1;
}
I have a IEnumerable<MyNode>. I want to get a list of all MyNode (...
- 9,302
115
votes
12
answers
103k
views
Why DFS and not BFS for finding cycle in graphs
Predominantly DFS is used to find a cycle in graphs and not BFS. Any reasons? Both can find if a node has already been
visited while traversing the tree/graph.
- 1,283
109
votes
11
answers
76k
views
Convert a series of parent-child relationships into a hierarchical tree?
I have a bunch of name-parentname pairs, that I'd like to turn into as few heirarchical tree structures as possible. So for example, these could be the pairings:
Child : Parent
H : G
F : G
...
- 96.6k
106
votes
7
answers
64k
views
Is there a module for balanced binary tree in Python's standard library?
Is there a module for an AVL tree or a red–black tree or some other type of a balanced binary tree in the standard library of Python?
- 12.4k
95
votes
6
answers
36k
views
How to render a tree in Twig
I would like to render a tree with an undetermined depth (children of children of children, etc.). I need to loop through the array recursively; how can I do this in Twig?
- 1,053
93
votes
3
answers
50k
views
Using self.xxxx as a default parameter - Python [duplicate]
I'm trying to simplify one of my homework problems and make the code a little better. What I'm working with is a binary search tree. Right now I have a function in my Tree() class that finds all the ...
- 1,179
91
votes
10
answers
54k
views
ASCII Library for Creating "Pretty" Directory Trees?
Is there some *nix tool or perl/php library that will let you easily create directory tree visualizations that look like the following?
www
|-- private
| |-- app
| | |-- php
| | | |...
- 165k
91
votes
5
answers
140k
views
looping through an object (tree) recursively
Is there a way (in jQuery or JavaScript) to loop through each object and it's children and grandchildren and so on?
If so... can I also read their name?
Example:
foo :{
bar:'',
child:{
...
- 17.4k
91
votes
4
answers
61k
views
Difference between Tries and Trees?
I remotely remember that tries don't store the whole data per node, only the suffix to the parent node.
Where trees do store the whole data, but only organize themselves based on a prefix.
So tries ...
- 29.5k
91
votes
5
answers
30k
views
Worst case in Max-Heapify - How do you get 2n/3?
In CLRS, third Edition, on page 155, it is given that in MAX-HEAPIFY,
The children’s subtrees each have size at most 2n/3—the worst case
occurs when the bottom level of the tree is exactly half ...
- 25.7k
90
votes
5
answers
34k
views
Calculate minimal operations to make two tree structures identical
This is more of a CS question, but an interesting one :
Let's say we have 2 tree structures with more or less the same nodes reorganized. How would you find
any
in some sense minimal
sequence of ...
- 18.5k
89
votes
11
answers
220k
views
With ' N ' no of nodes, how many different Binary and Binary Search Trees possible?
For Binary trees: There's no need to consider tree node values, I am only interested in different tree topologies with 'N' nodes.
For Binary Search Tree: We have to consider tree node values.
- 1,713
88
votes
4
answers
31k
views
When to choose RB tree, B-Tree or AVL tree?
As a programmer when should I consider using a RB tree, B- tree or an AVL tree?
What are the key points that needs to be considered before deciding on the choice?
Can someone please explain with a ...
- 983
87
votes
13
answers
195k
views
Difference between "Complete binary tree", "strict binary tree","full binary Tree"?
I am confused about the terminology of the below trees, I have been studying the Tree, and I am unable to distinguish between these trees:
a) Complete Binary Tree
b) Strict Binary Tree
c) Full ...
- 1,488
86
votes
8
answers
50k
views
When to use Binary Space Partitioning, Quadtree, Octree?
I have recently learned about binary space partitioning trees and their application to 3d graphics and collision detection. I have also briefly perused material relating to quadtrees and octrees. ...
- 5,985
84
votes
6
answers
181k
views
Tree plotting in Python
I want to plot trees using Python. Decision trees, Organizational charts, etc. Any library that helps me with that?
- 1,155
84
votes
9
answers
53k
views
Difference between red-black trees and AVL trees
Can someone please explain what the main differences between these two data structures are? I've been trying to find a source online that highlights the differences/similarities, but I haven't found ...
- 3,798
78
votes
11
answers
259k
views
How to search JSON tree with jQuery
I have a question about searching the JSON for the specific information. For example, I have this JSON file:
{
"people": {
"person": [
{
"name": "Peter",
...
- 1,505
78
votes
13
answers
62k
views
What type of NoSQL database is best suited to store hierarchical data?
What type of NoSQL database is best suited to store hierarchical data?
Say for example I want to store posts of a forum with a tree structure:
original post
+ re: original post
+ re: original post
...
- 90.7k
72
votes
4
answers
116k
views
Makefile issue: smart way to scan directory tree for .c files
I am doing a project which is growing pretty fast and keeping the object files up date is no option. The problem beyond wildcard command lies somewhere between "I do not want recursive makefiles" and "...
- 6,838
71
votes
6
answers
57k
views
Hitting Maximum Recursion Depth Using Pickle / cPickle
The background: I'm building a trie to represent a dictionary, using a minimal construction algorithm. The input list is 4.3M utf-8 strings, sorted lexicographically. The resulting graph is acyclic ...
- 82k
69
votes
9
answers
73k
views
How to represent a data tree in SQL?
I'm writing a data tree structure that is combined from a Tree and a TreeNode. Tree will contain the root and the top level actions on the data.
I'm using a UI library to present the tree in a windows ...
- 1,019
60
votes
6
answers
37k
views
Why Java Collection Framework doesn't contain Tree and Graph
I am familiar with Java Collection Framework which contains basic interfaces: Collection and Map. I am wondering why the Framework doesn't contain structures as Tree and Graph which are basic ...
- 31.7k
59
votes
8
answers
64k
views
How do I print out a tree structure?
I'm trying to improve performance in our app. I've got performance information in the form of a tree of calls, with the following node class:
public class Node
{
public string Name; // method ...
- 25.7k
56
votes
4
answers
53k
views
What are the known ways to store a tree structure in a relational DB? [closed]
There is the "put a FK to your parent" method, i.e. each records points to it's parent.
Which is a hard for read actions but very easy to maintain.
And then there is a "directory structure key" ...
- 53.1k
56
votes
4
answers
30k
views
What is the difference between a node and a vertex?
What is the difference (if any) between a node and a vertex? I can't find the answer after looking at countless sites! Even my book doesn't specify it so I am kind of lost!
It is worth mentioning ...
- 20.2k
55
votes
9
answers
103k
views
create array tree from array list [duplicate]
i have a list like this:
array(
array(id=>100, parentid=>0, name=>'a'),
array(id=>101, parentid=>100, name=>'a'),
array(id=>102, parentid=>101, name=>'a'),
array(id=...
- 1,309
55
votes
14
answers
74k
views
Build a tree from a flat array in PHP [duplicate]
I've looked around the internet and haven't quite found what I'm looking for. I have a flat array with each element containing an 'id' and a 'parent_id'. Each element will only have ONE parent, but ...
- 593
55
votes
5
answers
107k
views
Is there pointer in C# like C++? Is it safe?
I'm writing an application that work with a tree data structure. I've written it with C++, now i want to write it by C#. I use pointers for implementing the tree data structure. Is there a pointer in ...
- 22.6k
54
votes
6
answers
64k
views
What javascript tree data structures are available? [closed]
Are there good libraries for manipulating trees in javascript? Just to be clear, I am looking for tree as in data structure not display model.
- 4,268
54
votes
19
answers
14k
views
Python: simple list merging based on intersections
Consider there are some lists of integers as:
#--------------------------------------
0 [0,1,3]
1 [1,0,3,4,5,10,...]
2 [2,8]
3 [3,1,0,...]
...
n []
#--------------------------------------
The ...
- 8,348
52
votes
5
answers
32k
views
tree command on osx bash
I'm following a screen cast on a ruby gem called pry. At 8:10, the .tree command is used, which I believe is a Unix command.
It does not appear to be working on my system:
[24] pry(main)> .tree
\...
- 21.5k