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.
837
questions
2
votes
0answers
18 views
Traversing a tree with two types of nodes, while keeping track of all ancestors
I wrote code that stores an AWS Organization tree in a tree data structure in Rust. From the tree, I use a slightly modified preorder traversal algorithm to print all of the accounts in the ...
4
votes
1answer
66 views
Suffix Tree in Python
I was wondering why the following implementation of a Suffix Tree is 2000 times slower than using a similar data structure in C++ (I tested it using python3, pypy3 and pypy2). I know the bottleneck is ...
3
votes
1answer
59 views
LeetCode: Most Frequent Subtree Sum
My solution to LeetCode problem Most Frequent Subtree Sum works, but I have several questions regarding the code. I am also looking for an advice on how to improve the code.
Problem:
Given the ...
1
vote
1answer
27 views
5
votes
2answers
87 views
Binary Tree Preorder Traversal
What is the best way to move _add and _preorder methods in class Node to ...
4
votes
3answers
75 views
LeetCode: Validate Binary Search Tree C#
I was struggling with this question for many times,
and I have solved it every time, because I understand the concept.
but I can never get to a good concise solution which is easy to follow.
In a ...
1
vote
2answers
82 views
Binary tree pruning with BFS
Below the text of the exercise:
We are given the head node root of a binary tree, where additionally
every node's value is either a 0 or a 1.
Return the same tree where every subtree (of the ...
3
votes
1answer
74 views
Parsing Binary Tree Array in Python
I got this from a practice problem set, and looking for feedback on my approach.
Suppose you're given a binary tree represented as an array. Write a function that determines whether the left or ...
4
votes
0answers
55 views
JavaScript AVL Tree
I have been working through Introduction to Algorithms 3rd Edition, and have implemented an AVL tree through prototypal inheritance. The code presented here does work as expected based on the tests ...
2
votes
2answers
73 views
Iterative “post order” tree traversal [closed]
I wanted to get feedback on the correctness and efficiency of this post order traversal routine that my wife and I find really easy to grasp.
...
4
votes
1answer
58 views
Manipulate a tree layer wise
I built a tree in Haskell where every node has a number that is unique in its path from root to leaf. Nodes have a dedicated list for children that are leaves. ...
4
votes
3answers
139 views
2
votes
1answer
65 views
Python Fenwick Tree
I am trying to solve this question: https://open.kattis.com/problems/fenwick
A Fenwick Tree (also known as a Binary Indexed Tree) is a data
structure on an array which enables fast (𝑂(log𝑛)) ...
3
votes
1answer
93 views
F# Binary Tree and Tree Traversal
So for an side exercise on exercism I implemented a BinarySearchTree.
I was confident in implementing the creation of the binary tree. But I'm very unsure about the traversal of the tree. So I came ...
5
votes
1answer
95 views
Calculating the average of all nodes in a Binary Search Tree using visitors
I'm required to calculate the average value of all nodes in a BST using a Visitor, I'm not sure if I did this correctly or if i could just calculate the average ...
3
votes
1answer
64 views
Simple tree addition implementation
I am trying to learn Rust and I feel like a dummy every step of the way.
I went through the tutorial on making lists in Rust. I am trying to apply the knowledge ...
1
vote
1answer
50 views
Don't include root directory in HTML tree
I've written a function to create an HTML tree from JSON.
...
3
votes
2answers
77 views
Performance Improvement for Subtree for another tree
I was doing this algo on leetcode: https://leetcode.com/problems/subtree-of-another-tree/
Question:
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and ...
12
votes
4answers
1k views
Extraction of value from a dict-tree, given a path of arbitrary length
Problem: We read a complex json-file which grants us a tree in terms of a python "dict of dicts". We're then requested to retrieve a specific path from the tree, represented by a list of elements. The ...
1
vote
0answers
36 views
BST range search
I'd like some input on my implementation of bst-range, which follows below.
Before we can get to bst-range, we first need some setup code to build the BST.
(You ...
10
votes
2answers
715 views
Iterator for traversing a tree [v2]
this is an update of the implementation after I followed the feedback from Iterator for traversing a tree. After that I did changed quite a bit on the design and decided to ask for another round of ...
3
votes
1answer
68 views
6
votes
1answer
48 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 ...
3
votes
2answers
166 views
LeetCode: Diameter of Binary Tree
https://leetcode.com/problems/diameter-of-binary-tree/
Given a binary tree, you need to compute the length of the diameter of
the tree. The diameter of a binary tree is the length of the longest
...
1
vote
0answers
51 views
leetcode 230: kth smallest element in a Binary Search Tree
Here is my implementation: the goal of the algorithm is to find the kth smallest element in a BST.
...
1
vote
1answer
209 views
Ternary search tree implementation in python 3
I have implemented a Ternary search tree. It works well. But if you think something needs to be improved, say it. This code was tested in Python 3.7.4.
...
4
votes
2answers
197 views
Heap Sort and Binary Tree Sort Algorithms (Python)
Heap Sort
A Binary Heap is a Complete Binary Tree where the items are stored in a special order such that the value in a parent node is greater or smaller than the two values in the children nodes.
...
1
vote
1answer
93 views
Flatten binary tree to linked list
I'm trying to flatten a binary tree into a linked list.
I have a working, correct solution:
...
3
votes
2answers
167 views
Binary Search Tree implementation in Python 3
Please review my BST Code
1. Class node
class Node:
2. Constructor
...
4
votes
2answers
218 views
Build a flat List from a Tree structure in Java
I have a Tree structure represented by a List, which I want to get it flattened.
I wrote the function below:
...
4
votes
2answers
194 views
LeetCode: House Robber III C#
https://leetcode.com/problems/house-robber-iii/
Please review for performance
The thief has found himself a new place for his thievery again. There
is only one entrance to this area, called the "...
5
votes
3answers
60 views
Symmetric Tree Check in Python
Inspired by This LeetCode Question.
Instead of checking if every layer is symmetric, it instead checks if any aren't. This allows the program to leave early is an early layer fails the test. I'm ...
4
votes
1answer
71 views
LeetCode: Symmetric Tree C#
https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/627
Given a binary tree, check whether it is a mirror of itself (ie,
symmetric around its center).
For ...
5
votes
2answers
119 views
LeetCode: Binary Tree Zigzag Level Order Traversal C#
https://leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/787/
Given a binary tree, return the zigzag level order traversal of its
nodes' values. (ie, from ...
3
votes
1answer
42 views
Javascript Tree Class 2
This question is the second version of the code here.
I'm writing a general tree class. Specifically, each node should have oen parent, some number of children, and hold a value.
I'm looking for ...
4
votes
2answers
103 views
Data structure that retrieves each item with a specified probability
I wanted a data structure that allowed me to set the chances of randomly returning each of it's elements.
For example, suppose I have a Human class. Every Human has an attribute called eyeColor. I ...
3
votes
1answer
87 views
Convert a Binary Tree to Doubly Linked List
Challenge
Link on geeksforgeeks: Binary Tree to DLL
Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL)
In-Place. The left and right pointers in nodes are to be used as
previous ...
3
votes
2answers
104 views
Javascript Tree Class
I got caught in the trap of implementing my own data structure. I've created a very general tree structure, where each node gets one parent, some children, and holds a value.
I'm mostly looking for ...
2
votes
1answer
39 views
Convert Sorted Array to Height Balanced Binary Search Tree
Algorithm
This is my code to convert a sorted vector of integers to a balanced binary tree of the same content.
The binary tree is made of these nodes:
...
-1
votes
1answer
223 views
Python 3 code for a binary search tree [closed]
I am working on a python3.6.5 question about BST:
Binary search tree (BST) is a binary tree where the value of each node is larger or equal to the values in all the nodes in that node's left ...
8
votes
1answer
165 views
An array with \$O(\log\ n)\$ time complexity for all operations
Does this exist already? It's an array (=variable-size list with integer indices) where add/remove/set and get all take \$O(\log\ n)\$ time.
I couldn't find this anywhere, so I made up the name "Log-...
5
votes
1answer
172 views
TreeView class in WPF class
We are converting a WinForms application to WPF. so I need to accept the input like WinForms. As I don't want to change the logic of it. Ao I write the class for those its works. But the is not good ...
4
votes
1answer
72 views
Maximum profit earned on weighted un-directed tree
I came across this problem while giving a sample test.
The problem was that we have given a tree which is undirected. We can
start from any node of our choice. Initially we have power "P" and
...
6
votes
2answers
652 views
Javascript - Find a deepest node in a binary tree
Problem Statement
Given the root of a binary tree, return a deepest node.
For example, in the following tree, return d.
a
/ \
b c
/
d
My ...
3
votes
1answer
64 views
Generic Fenwick Tree
A Fenwick Tree, or a Binary Indexed tree, is an interesting data structure that can efficiently update its elements. You can read more about it in this paper.
Here is a generic implementation of a ...
2
votes
1answer
288 views
Simple dynamic tree in Python
I tried to make a dynamic tree in python. It is simple and i have gotten it to work so far. I created a function in main that generates some example data for the tree and then the main goal was to ...
1
vote
0answers
114 views
Quadtree implementation in Rust
To teach myself Rust, I implemented a simple Quadtree over 2D points with insert, delete, ...
9
votes
2answers
2k 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:
...
5
votes
1answer
89 views
Unbalanced search tree for comparing multiple string arrays
I have a system that stores resources. A resource contains a string that represents a user role, for example "3".
With this user role "3", you can retrieve a list of permissions for the user role, ...
2
votes
1answer
76 views
Implementation of Generic Binary Tree Code
I'm in the process of independently learning Generics as a way to build on a college assignment for Binary Search Tree. I've completed this program without Generics first and now I've converted over ...
