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
611 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
260 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
387 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
9k 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'...
7
votes
1answer
3k 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
605 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
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 ...
6
votes
1answer
48 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: ...
5
votes
1answer
72 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
1k 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
626 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
55 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
10k views

DFS in Binary Tree

I have written this code for DFS in a binary tree and would like improvements on it. ...
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 ...
13
votes
3answers
4k 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: ...
10
votes
1answer
658 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
788 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
3k 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? ...
4
votes
1answer
1k 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 ...
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
2k 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. (...
10
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
168 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
923 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
396 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
1answer
199 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 ...
5
votes
1answer
512 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
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 ...
4
votes
1answer
471 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
197 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. ...
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 ...
3
votes
3answers
360 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. ...
3
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 ...
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
91 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 ...
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. ...
1
vote
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 ...
10
votes
2answers
155 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
726 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
0answers
364 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: ...
6
votes
2answers
6k 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
3answers
6k 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 ...
6
votes
1answer
574 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 ...