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
63
votes
1answer
2k 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 ...
28
votes
2answers
57k views

Recursion vs iteration of tree structure

Some recursive code is part of a particularly slow path of a project. Out of curiosity I was playing around with reimplementing the code using stack context iteration instead of recursion. Below are ...
27
votes
3answers
26k views

Quadtree implementation

I've implemented a quadtree in C++. Ignore any apparent similarity to the pseudocode on Wikipedia, it's all in your head, I swear. How can I improve it? Algorithm speed/space improvements, any extra ...
24
votes
2answers
636 views

Where equations are born and mutants are buried

I've read up on genetic programming yesterday so I figured I'd try to implement something myself. I would like the main focus to be on whether or not I've implemented the idea behind it correctly. ...
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. (...
15
votes
1answer
649 views

C# Treap implementation

I recently developed a simple treap data structure in C#. In the future, I may have the class extend IDictionary. For now, I only expose a public accessor and a ...
15
votes
3answers
3k views

Quadtree design

I have an application which is used for displaying and modifying huge volumes of point cloud data from lidar files (up to few gigabytes each, sometimes loaded in simultaneously). In the app the user ...
14
votes
3answers
22k views

Building a Tree from a flat List<Nodes>

This is my incoming data: ...
14
votes
2answers
2k views

Free a binary tree without using recursion or allocating memory

As the title says, the objective is to free a binary tree without using the stack or allocating memory. This was required for a kernel module where resources were limited. Result has a complexity of \...
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 ...
14
votes
1answer
2k views

Prim's algorithm for minimal spanning trees

I want to write an article giving a Haskell introduction specifically to Java developers, and would like to get feedback on my implementation. Please keep in mind that I don't want to be "too clever", ...
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: ...
13
votes
4answers
4k views

Binary Search Tree - C++

I'm implementing several data structures in an attempt to learn C++. Below is a binary search tree that I've implemented to learn about pointers, dangling pointers, and memory leaks. I was hoping ...
13
votes
1answer
399 views

Is this a BSP tree? Am I missing something?

I've been practicing using BSP trees as I hear they are a good start to create procedural spaces such as houses. For ease-of-deployment purposes, I've tested this code in Lua and it seems to work. ...
13
votes
1answer
438 views

N-dimensional maze generation with octrees and pathfinding

I did a maze thing ages ago that could support any number of dimensions, but it was very slow to generate. To get an idea of how it generally works with the multiplier and stuff, here's a gif of ...
12
votes
4answers
51k views

Simple Binary Search Tree

At the moment I am learning algorithms and here I am trying to implement a simple binary search tree. I would like to know your suggestions on whether I am on the right track or not, and how this can ...
12
votes
5answers
2k views

Binary tree encoding

I implemented a solution to this coding challenge on the Code Golf. I have decent experience with C/C++, but it's been a while since I've used them extensively. ...
12
votes
3answers
12k views

Suffix tree implementation in Java

I was trying to solve the problem where given a larger string and an array/list of smaller string, we need to make the determination whether the larger string contains each of the smaller strings. I ...
12
votes
3answers
1k views

Huffman tree compressing/decompressing in C

In a past course one of the assignments was to write a program that can compress files using Huffman Tree algorithm, and uncompress the files that the program generates. My design is to count the ...
12
votes
2answers
4k views

Validating a Binary Search Tree

This is an implementation of a function to check the property of a Binary Search Tree, that is: the key in any node is larger than the keys in all nodes in that node's left subtree and smaller ...
12
votes
1answer
4k views

Binary Tree Implementation in Rust

To teach myself Rust, I implemented a naive binary tree with support for insert, delete and lookup operations as well as in-order iteration. I'm still a little rusty (no pun intended) when it comes ...
12
votes
1answer
3k views

2D Bin Packing Algorithm Implementation

I wrote a 2D greedy bin packing algorithm using Python 3.6 Heres a quick summary: The algorithm consists of two classes (which I will attach at the end of this file along with a link to my github ...
12
votes
2answers
2k views

In-memory B-Tree in C++11

I just wrote a simple B-Tree insertion implementation, and was wondering if anyone can comment / critique on code style, readability, maintainability etc. I tested it with a few small test cases and ...
12
votes
0answers
502 views

Binary Search Tree Monad Implementation

I've written a Binary Search Tree Monad in Scala. I would like to hear your thoughts on how to improve it (e.g. making insertion/deletion/search faster and more scalable). Also, is there a better way ...
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, <...
11
votes
2answers
17k views

Tree Template Class Implementation for C++

I have not done any parameter checking, however I think the meat of the class is there. Let me know what you think. ...
11
votes
3answers
3k views

Red Black Tree Implementation

I would like some feedback on my red black tree implementation. Anything is fine. I've debugged this and it seems to be working fine, however I may have missed something. Basically, this is a red ...
11
votes
1answer
2k views

Yet another minimax tree for TicTacToe

I have written a working minimax tree for Tic-Tac-Toe. What I have done so far is create a tree with end node having value 10, 0 or -10 base on win, lose or draw. After I create a tree I then ...
10
votes
3answers
27k views

Creating a binary search tree

I want you to pick my code apart and give me some feedback on how I could make it better or simpler. Although, agree that generics should be used, instead of integers, let's punt on generics as a ...
10
votes
3answers
769 views

Check if all leaves are at same level in a binary tree

I have written this code for checking whether all leaves are in the same level or not, in a binary tree. Any suggestion or improvement is appreciated. ...
10
votes
4answers
1k views

Do I need Generics for these node and tree classes?

I want to implement KD tree. I have defined class Node as follows: ...
10
votes
3answers
1k views

Find the common ancestor between two nodes of a tree

Here is my code in Python for to find a common ancestor between two nodes in a particular tree. This is a question from Cracking the Coding Interview that I decided to implement on my own. No one has ...
10
votes
4answers
3k views

Determine if a binary tree is balanced

I'm currently running through some Cracking the Coding Interview questions and my solution to 4-4 is quite different from any of the given solutions. The question asks to determine if a given binary ...
10
votes
2answers
2k views

Run time complexity of printing a binary tree level by level

I have some doubts about running time of following question. The problem is printing a binary tree level by level. For example if tree is like ...
10
votes
2answers
157 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 <...
10
votes
1answer
648 views

Maximum element in a binary tree

This method finds the maximum in a binary tree. I have used generics to make this code more usable. However, I am not sure if I have written efficient and good Java code. This is a method inside a ...
10
votes
1answer
167 views

Good performance when predicting future game states

This question is about my answer to this king-of-the-hill challenge on Code Golf. In short, the purpose of the challenge is to code a slime that, trough various possible moves gains control over an ...
10
votes
1answer
676 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 ...
10
votes
1answer
3k views

Matrix to Tree Algorithm

The code takes a matrix and turns it into a tree of all the possible combinations. It then "maps" the tree by setting the value of the ending nodes to the total distance of the nodes from beginning ...
10
votes
1answer
283 views

Binary Tree/ Amorphous Binary Tree Creator

I suppose this is a two-part question. The first part is just a simple implementation of a Binary Tree (BTree), with pre-order, post-order, and in-order searches ...
9
votes
4answers
60k views

Binary Search Tree C++ Implementation

I've implemented a simple binary search tree for practice purposes: ...
9
votes
2answers
672 views

Recursive search on Node Tree with Linq and Queue

This code is now maintained on GitHub I've created a Node class which contains two important properties: ...
9
votes
3answers
3k views

Binary tree in Python exercise

I'm practicing Python. Being completely new to the language I'd like to hear someone else thoughts on the way I use the language. I'm coming from (mainly) Java and C so I'd expect new ways of doing ...
9
votes
1answer
5k views

Binary tree in Python

As a Python newbie, I have coded this binary tree as best as I could to follow Python idioms. However, I know it is still very verbose and not up to standard. I would like Python experts to tear this ...
9
votes
1answer
1k views

Generic domain independent Monte Carlo Tree Search methods library

I've written this small generic library for the purpose of my Bachelor's thesis. It's fully functional and unit tested and I want to get as many opinions as possible regarding overall code quality (...
9
votes
1answer
4k views

Small C++ Boost extension based on boost::property_tree

This is a small extension based on a boost::property_tree, which supports arbitrary values for the properties and appropriate serialization. It can be used as an ...
8
votes
4answers
2k views

Recursive binary search tree - follow-up

This is a follow-up to Recursive binary search tree changes: Used raw pointers rather than std::unique_ptr const correctness Made variable names more beautiful implemented at() How can I improve ...
8
votes
1answer
50k views

Binary search tree implementation in C++

I've written a BST implementation and would like a code review and any suggestions on how to make it better. ...
8
votes
3answers
2k views

Print all nodes that are at distance k from a leaf node

Given a binary tree and a positive integer \$k\$, print all nodes that are distance \$k\$ from a leaf node. Here, the meaning of distance is different from the previous post. Here, \$k\$ is ...
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 ...