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.
2
votes
1answer
57 views
Check binary tree symmetry by reversing, checking equality, coverage tested, makefile
A few weeks ago I recall a HackerNews story (found it again: "I Don't Want to Hire You If You Can't Reverse a Binary Tree") about reversing a binary tree (with, as I remember it, the end goal being to ...
4
votes
1answer
48 views
Managing IDs using AVL trees
In a txt file there are IDs and next to them there are their neighbours like this:
1 1
1 2
1 3
2 1
2 4
2 8
3 5
Using AVL trees I store the IDs in one AVL ...
-6
votes
0answers
31 views
traverse through binary tree and print list [closed]
New here! Trying to traverse through a binary tree in level order (breadth first traversal). I have written code but I get a different output to what is desired.
The tree
...
2
votes
1answer
58 views
Mirror image of a binary tree
I wrote a small routines to create a mirror for any binary tree. I am just sharing my necessary routines instead of full class. could you please let me know your comments on this. I just curious to ...
3
votes
0answers
61 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
3answers
444 views
Finding the tree height in Python
I'm trying to get an efficient algorithm to calculate the height of a tree in Python for large datasets. The code I have works for small datasets, but takes a long time for really large ones (100,000 ...
4
votes
2answers
375 views
Inorder, Preorder, and Postorder traversal of a binary tree in C++
I am a newbie in this world of data structures and algorithms (returning to these topics after 5 long years). Can someone please check if the code I have written for Binary Tree is OK?
Test-case
10, ...
1
vote
1answer
58 views
Traversing a Binary Search Tree in Swift
I'm implementing the Binary Search Tree data structure in Swift. It looks like this:
...
5
votes
1answer
47 views
Speed concerns of octree implementation
For couple of days now I am trying to speed up my Force-Directed graph implementation. So far I've implemented Barnes-Hut algorithm that's using octree to decrease number of computations. I've tested ...
0
votes
1answer
29 views
Follow-up zp-Tree to represent Trees as nested arrays: 3rd (final?) revision
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 a third (final?) review on the modified code if ok.
Note: ...
0
votes
1answer
21 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 ...
1
vote
1answer
49 views
1
vote
1answer
42 views
zp-Tree library to represent trees as nested arrays
For my project I have rewritten a small lib for a tree structure that was inspired by wangzuo's js-tree.
The reason was largely because I prefer to work with an array structure rather than nested ...
0
votes
0answers
18 views
Lazy segment tree implementation
I wrote a C++ implementation of a segment tree (I wrote it for an arbitrary function, "lazy" version) and I want so much to ask for a review. I'd like to know how I can make it better, especially the ...
0
votes
0answers
42 views
Segment tree implementation in C++
I wrote a C++ implementation of a segment tree (I wrote it for an arbitrary function, not "lazy" version) and I want so much to ask for a review. I'd like to know how I can make it better, especially ...
-1
votes
1answer
46 views
3
votes
3answers
179 views
Building prefix tree from dictionary, performance issues
I'm trying to build a prfix tree. So, using the following dictionary 'and','anna','ape','apple', graph should look like this:
I've tried 2 approaches: using ...
1
vote
0answers
45 views
Binary search tree class in Java
I am trying to create a binary search tree class in Java and am wondering how I did. I am fairly confident on most of the methods, but fear I may have messed up the delete method. I know I am ...
3
votes
0answers
60 views
Check if a binary tree is a binary search tree or not
This checks if both the left and right subtrees are binary search trees. If they are, then it compares the nodes data with the maximum element in the nodes' left subtree and minimum element in the ...
2
votes
1answer
28 views
Verify that a binary tree is balanced
A binary tree is balanced if both its children are balanced and the difference between the heights of its children is at most 1.
...
4
votes
1answer
83 views
Implementing Binary Tree using Queue in C#
I am in the process of learning data structures and I am trying to implement Binary Tree using Queue in C#.
Below are my Tree implementation classes.
...
0
votes
2answers
84 views
Summing all keys in the leaves of a tree
My program takes 35 sec to run example 2. How can I make my program faster?
...
0
votes
1answer
46 views
Common ancestor in a binary tree
This method finds the common ancestor of two nodes in a binary tree.
Any style suggestions or ways to make it more idiomatic? Is the algorithm correct? Rubocop says the cyclomatic complexity is too ...
1
vote
1answer
103 views
A basic pure Python hash map using a tree
I would like feedback on my first attempt to understand how hash tables work. I've read some on how hash tables use modulo operations to find the location of a key.
Can you help me understand, ...
5
votes
0answers
56 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 ...
1
vote
2answers
56 views
Next node of a node in Binary search tree
To find the node next to a given node we need to consider two cases.
case 1: if the node has a right subtree then return the min node in its right subtree.
case 2: if the node doesn't have a right ...
0
votes
1answer
50 views
Create a binary search tree from a sorted array (increasing order)
Description:
Since the input array is sorted, we can take the middle element of the array to be parent and recursively do the same on the left and right halves to create left and right sub trees of ...
0
votes
1answer
42 views
Create D lists of nodes where D is the depth of the binary tree
I have used a HashMap of ArrayLists to maintain the nodes at each depth.
Also i maintained a depth at each node in the binary tree by using a HashMap that stores . While traversing the tree in a ...
3
votes
2answers
47 views
Simple Octree implementation
I've implemented a rather straightforward octree, but I don't feel that good about the coding style or some of the implementation. In particular, I use some nasty ...
0
votes
0answers
54 views
AVL Tree Array Representation
In a school assignment I'm supposed to create a program simulate insertion, deletion, count nodes, and delete tree algorithm and displays the traversal, level order, and array representation of it. ...
4
votes
1answer
48 views
Classification tree in Swift
As an effort to teach myself Swift as well as to get familiar with machine learning algorithms, I've been trying to implement common algorithms, starting with a Random Forest. This is, for the moment ...
1
vote
3answers
183 views
Priority Queue (Binary Search Tree) Implementation
I have made a Priority Queue implemented as a Binary Search Tree. I would appreciate comments related to optimization and proper functionality, but any comments/critiques are welcome.
PQ.h:
...
6
votes
1answer
678 views
Breadth-first search on a tree in Python
The following code performs breadth first search on a mockup tree
...
1
vote
1answer
94 views
Find pairs in binary search tree in which sum of nodes keys is equal key
There is a task:
Given a binary search tree of \$n\$ nodes, find all the pair of nodes whose sum is equal to a given number \$k\$ in \$O(n)\$ time and constant space.
Please let me know if you ...
2
votes
1answer
53 views
Counting the number of increasing sub-sequences
The problem is to find the number of increasing sub-sequence of a string with only digit characters.
Answer may be very large, so output it modulo 10^9+7.
I have been able to get a O(n) solution ...
3
votes
1answer
66 views
Design of tree data structure
I am practicing for technical interviews and I am encountering a lot of problems relating to the tree data structure. I have gone through other posts that discuss about the tree data structure and ...
3
votes
1answer
67 views
Josephus permutation - follow up
Follow up of this question
Changes:
The pop_min function now panics if the tree is empty.
Moved the size attribute to the ...
4
votes
1answer
91 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 ...
0
votes
0answers
46 views
Red-black tree rotation
I am unfamiliar C coding styles and I had an idea to use a function pointer for this given piece of code. Typically, would it be aligned with current C coding style to use function pointers here or ...
0
votes
1answer
44 views
Tree processing for series and parallel execution
I have a tree processing application where some of the nodes are "executed" in parallel and some in series. I managed to do this but I feel that the solution looks a bit "hacked up" and can be ...
1
vote
1answer
74 views
2
votes
1answer
99 views
Java Tree Implementation
I wrote a simple tree data type in Java consisting of nodes which are themselves trees, and where each tree has its own list of children (not a binary tree). I plan on eventually using it in a minimax ...
4
votes
1answer
54 views
Construct binary tree from inorder and postorder traversal
The problem is taken from here. The tree is guaranteed not to have duplicate elements.
My questions is, instead of creating new arrays leftInOrder, ...
1
vote
1answer
23 views
Binary Search Tree insert while keeping track of parent for node to be added - iteration 2
Follow up question to
Binary Search Tree insert while keeping track of parent for node to be added
I am implementing a red black tree for fun and am wondering how I should modify my basic BST ...
1
vote
2answers
78 views
Finding all root-to-leaf paths in a binary tree
The task is to return all root-to-leaf paths, given a binary tree (from leetcode).
This is my approach.
Take a helper array and a counter, keeping track of what has been traversed so far. If it is ...
0
votes
1answer
26 views
Binary Search Tree insert while keeping track of parent for node to be added
This question has a follow up question:
Binary Search Tree insert while keeping track of parent for node to be added - iteration 2
I am implementing a red black tree for fun and am wondering ...
1
vote
1answer
38 views
Checking for items in sublists
Today I'll demonstrate a simple function that searches for a item in all sublists of a list. For this it uses iteration, and keep in mind that it can be slow because of this. How can I improve it? ...
18
votes
0answers
275 views
Printing binary trees
After writing this answer, I was inspired to try to design a more elegant solution to the problem of printing binary trees. And what better tool with which to seek elegance than Clojure?
Overall ...
2
votes
0answers
87 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:
...
1
vote
1answer
44 views
Check directed graph is tree or not
Here is my approach.
1. Checking there is no cycle.(Using BFS)
2. All nodes are connected. (visited)
...
