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.

Filter by
Sorted by
Tagged with
8
votes
2answers
946 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 ...
5
votes
2answers
345 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 ...
4
votes
1answer
423 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 ...
8
votes
3answers
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: ...
6
votes
2answers
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....
6
votes
3answers
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'...
8
votes
1answer
4k 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 ...
7
votes
1answer
639 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 ...
6
votes
1answer
49 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: ...
6
votes
3answers
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 ...
5
votes
1answer
73 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: ...
4
votes
3answers
2k 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 ...
3
votes
2answers
634 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 ...
2
votes
4answers
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 ...
0
votes
1answer
70 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 ...
8
votes
2answers
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 ...
5
votes
5answers
11k views

DFS in Binary Tree

I have written this code for DFS in a binary tree and would like improvements on it. ...
4
votes
1answer
2k 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 ...
14
votes
4answers
5k 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: ...
14
votes
1answer
9k 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 ...
10
votes
1answer
736 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 ...
8
votes
1answer
824 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 ...
5
votes
3answers
4k views

Recursive binary search tree

How is my usage of std::unique_ptr() and std::move()? How can I improve this code? ...
4
votes
2answers
2k 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? ...
2
votes
1answer
1k views

Create Binary, Balanced Tree

I wrote a function, which takes a list of Integers, and then makes a balanced binary tree. Please critique it. I'd like to know know how to make it more concise and idiomatic. ...
16
votes
3answers
4k 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. (...
11
votes
4answers
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, <...
6
votes
3answers
183 views

Tree abstraction

This code provides a Tree abstraction. I would like to finalize the code structure only in tree directory, before starting ...
6
votes
2answers
1k 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 ...
5
votes
1answer
714 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 ...
5
votes
1answer
456 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 ...
5
votes
3answers
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 ...
5
votes
1answer
205 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 ...
4
votes
1answer
5k 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 ...
4
votes
3answers
1k 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 ...
4
votes
1answer
599 views

Iterative Red-Black Tree (dynamic stack)

I've completely reworked the previous code, posted here, so that it is a bit more correct regarding dynamic memory management, and also a bit more true to the object-oriented paradigm. ...
4
votes
1answer
204 views

Least common ancestor (LCA) in a binary tree

Find the LCA in binary tree, where a node is also its own ancestor. This question is attributed to GeeksForGeeks. I'm looking for code review, optimizations and best practices. ...
3
votes
3answers
383 views

Kattis Challenge - Animal Classification

I'm new to competitive programming and C++ in general. I have solved the Kattis Animal Classification challenge. We are given two classification trees, each represented using nested parentheses. ...
2
votes
1answer
107 views

Find the shortest whole repetitive substring (part 2)

This is a continued improvement from discussion here (Find the shortest whole repetitive substring), since code has changed a lot dues to improvement, I post it here. Major smart ideas are from ...
2
votes
2answers
1k views

Print left view of the tree

Left view of a Binary Tree is set of nodes visible when tree is visited from left side. Left view of following tree is 12, 10, 25. ...
2
votes
1answer
1k views

Extract Leaves of a Binary Tree in a Doubly Linked List

Given a Binary Tree, extract all leaves of it in a Doubly Linked List (DLL). Note that the DLL need to be created in-place. Assume that the node structure of DLL and Binary Tree is same, only the ...
1
vote
1answer
3k views

Finding common ancestor in a binary tree

Following is a Python program I wrote to find the common ancestor in a binary tree (not BST) with no link to parent node. Please review. ...
1
vote
2answers
3k views

Serializing/deserializing binary tree in most space-efficient way

I'm looking for corrections, optimizations, general code review, etc. ...
10
votes
2answers
161 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 <...
8
votes
4answers
6k 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 ...
7
votes
2answers
732 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 ...
6
votes
2answers
7k 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? ...
6
votes
1answer
589 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 ...
6
votes
1answer
52 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 ...
6
votes
0answers
366 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: ...