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.
6
votes
1answer
608 views
Breadth-first search on a tree in Python
The following code performs breadth first search on a mockup tree
...
1
vote
1answer
75 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
50 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
56 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
54 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
74 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
43 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
37 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
67 views
2
votes
1answer
78 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 ...
2
votes
0answers
49 views
C++ segment tree implementation
I created my own implementation of Segment Tree structure. It works well, it is lazy, it supports arbitrary functions and is able to change the value of the whole segment fast.
But there are some ...
4
votes
1answer
46 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
19 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
60 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
20 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
35 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? ...
0
votes
0answers
44 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?
The ...
2
votes
0answers
44 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
32 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)
...
4
votes
2answers
92 views
2
votes
2answers
55 views
Make binary search tree from sorted array
Here is my code for converting a sorted array to a binary search tree. Please review and let me know the improvements or some better way of solving this.
...
3
votes
1answer
73 views
C++ Template Binary Search Tree
I've been trying to improve my C++ skills as well as work on some general coding techniques so I've attempted to build my first binary search tree in C++ using templates. I've mostly done Java ...
3
votes
2answers
112 views
Finding if the tree is balanced or not
Can someone please review my code and let me know if there are some bugs or possible improvements?
...
1
vote
0answers
32 views
Persistent set (Red black tree) - follow up
Follow up of this question
Things I changed:
Fixed some typos
Renamed variables and method to more descriptive names.(Eliminated 1 letter variables)
Added static method ...
2
votes
1answer
70 views
Persistent set (Red black tree)
This is a partially persistent data structure using a red black tree. It will copy \$O(lg(n))\$ items for each remove or add operation.
...
6
votes
1answer
64 views
Alpha Beta Pruning Optimization
I made a class that would do alpha beta pruning on a binary tree of 40 degree. However there is a time limit on a single move of 30 seconds. I am to play against my professor and his opponent class. I ...
1
vote
0answers
32 views
TreeNode with nested super as parent
I found a way to use the JLS as a tree-structure (at least in let the parent-field disappear).
Please ignore the main-method.
It works, but from OOD would you say this is ok?
...
3
votes
1answer
45 views
Alpha Beta Pruning with binary tree of size 40
I'm working on a program that is supposed to use alpha beta pruning to find the best move for a game. The game is basically a binary tree of degree of 40 and each node will have a different float ...
2
votes
1answer
56 views
AVL tree implementation in Python
Is my implementation of AVL tree correct? It is my second Python program and I am not sure if do code properly.
...
4
votes
2answers
98 views
Binary search tree in Java with only one class
I have written a BST using one class. Is my code okey or something could be better?
...
9
votes
1answer
80 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 ...
4
votes
1answer
54 views
SICP - exercise 2.69 - generate a huffman tree from a set of ordered leaves
From SICP
Exercise 2.69: The following procedure takes as its argument a list of
symbol-frequency pairs (where no symbol appears in more than one pair)
and generates a Huffman encoding tree ...
4
votes
2answers
53 views
Tree ADT implementation in C
As a learning exercise, I decided to implement a BST and add functionality to it slowly. I'd appreciate any feedback.
I should also point out that I borrowed the template from the here.
...
4
votes
2answers
58 views
Binary search traversal with in/pre/post order and BFS/DFS
I have the following code for the BST for the inorder, postorder, preorder, breadth first and depth first traversals. Can you review and let me know the optimisation points and issues, if any?
...
5
votes
1answer
70 views
Find if a given tree is subtree of another huge tree
The problem statement is:
You have two very large binary trees: Tl , with millions of nodes, and T2, with
hundreds of nodes. Create an algorithm to decide if T2 is a subtree of Tl.
A tree T2 ...
0
votes
0answers
23 views
Find Inorder successor and predecessor using window
There are plenty of complicated algorithms to find inorder successor and predecessor on internet, few of them even augment a parent pointer, I've tried in my algorithm to do it using simple recursive ...
5
votes
1answer
33 views
Converting Binary Tree to LinkedLists
The problem statement is :
Given a binary tree, design an algorithm which creates a linked list of all the
nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked
...
1
vote
1answer
83 views
Optimum Tree traversal algorithm Topcoder
I'm practicing a 1000 point algorithm problem on the topcoder.com arena.
The problem is as follows:
You work for an electric company, and the power goes out in a rather large apartment complex ...
3
votes
3answers
89 views
Small tree generator
If one enters, say, "2, j" then it prints:
j
jj
If there is no second it should be *, so if it's just 2, it's ...
3
votes
1answer
90 views
Minimalist Tree
While working on a small project, I tried to implement a super simple tree class in C++. It supports an arbitrary number of branches from each node.
In addition to general comments, my main concerns ...
3
votes
1answer
79 views
Prove that the graph is a valid tree in Python
I recently solved this leetcode problem:
Given n nodes labeled from 0 to n - 1 and a list of undirected edges
(each edge is a pair of nodes), write a function to check whether
these edges ...
8
votes
2answers
108 views
X'mas tree implementation
With the festive season mood and the new year coming, I thought I would make my first question this year, a tree implementation. Blame me because it doesn't have anything to do about Christmas.
...
10
votes
1answer
82 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 ...
3
votes
2answers
100 views
Python Tree/Node Class from scratch
I decided to try to make my own tree style class.
I may use it in a project, but it's primarily to practice.
I would appreciate any feedback for improvements, best practices, etc.
...
6
votes
2answers
302 views
C# FTP class for interaction with FTP server (Download only)
I'm writing my own FTPclient for downloading files from my FTPserver as a project. So far I can download and go backwards/forwards in the folders using this code.
How does it look? What could be done ...
7
votes
2answers
55 views
Function to find the minimum depth of a tree
For a leetcode problem to find the minimum depth of the binary tree, I have written the below solutions. The solution is accepted, but can I do any other changes to make the code elegent?
...
2
votes
2answers
86 views
Dictionary operations on a Binary Search Tree data structure?
today I tried to code all the dictionary operations such as Search, Successor, Predecessor, Minimum, Maximum, Insert, Delete etc. for a Binary Search Tree data structure using the Java programming ...
5
votes
2answers
103 views
Binary Search tree deletion optimization
I have just started implementing Binary Search tree on my own without using any tutorials online.
Please have a look and suggest how can I make code less cluttered and more faster. Right now I am ...
2
votes
0answers
45 views
Coloring trees in Elixir
The following is my tree coloring realisation attempted to get a feel of Elixir (simple, but slow coloring algorithm from Principles of Distributed Computing). Coloring runs from the root, using ...
4
votes
3answers
240 views
Python function to determine whether a given BST is valid
Here's a simple function I wrote using recursion. Does this run in \$O(n)\$ time and use \$O(n)\$ space, where \$n\$ is the number of nodes in the tree?
...