Questions tagged [binary-trees]

a rooted tree in which each node has no more than two children

Filter by
Sorted by
Tagged with
0
votes
1answer
13 views

Can you add up all the nodes of a special binary tree in polynomial time, in respect to the number of levels?

Let's say you have a binary tree defined by a group $S=\{a:[5,6],b:[7,67],c:[45,12],...\}$ (this group is just an example). The binary tree is constructed so that there are two starting parent nodes, $...
-1
votes
0answers
22 views

What are R trees? How it works?

I have just read about some data structure which are used rarely, one of them is R trees. I searched a little about it and found that it is used for spatial search. The Wikipedia page says that it can ...
-1
votes
0answers
28 views

How to write a Binary tree to a file in C++

I want to serialize a binary tree into a .txt file. I am traversing the tree using bfs, to be able to just multiply by 2 (or 2+1 for right child) to jump to a left child of a node, and I want to write ...
1
vote
3answers
65 views

How balanced is a binary tree in the average case?

For algorithms involving binary trees, time or space complexity is often O(logn) in the best case of a completely balanced tree, and O(n) in the worst case of a completely unbalanced tree. Sure, it's ...
0
votes
1answer
24 views

Reassigning BT root and its children

Given the root of a binary tree, for instance below, I am running the following tests in Python: 1 / \ 2 5 / \ 3 4 Test 1: ...
2
votes
1answer
25 views

Difference between Recursion Tree & Binary Tree

What's the difference? is a Recursion tree private case of Binary tree?
2
votes
3answers
231 views

For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes

in my notes I have one fact: in a binary tree with $n$ elements ($n$ divisible by three) there is a node $u$ such that the number of nodes in the subtree with root $u$ is at least $\frac{n}{3}$ and at ...
1
vote
1answer
87 views

prove that in binary heap buildheap function does at most 2N-2 comparison

prove that in binary heap buildheap function does at most 2N-2 comparison I don't know how should I prove it I need some hint thanks. buildheap procedure: we have n element and we build a heap at ...
2
votes
0answers
19 views

Repairing a perfect binary merkle forest

Let's say we have a forest of imperfect binary merkle trees of different heights (this is an invariant). Only the numbered nodes store data, the rest store hashes. Here is an example with 4 trees, ...
0
votes
1answer
20 views

Edge-disjoint paths in trees

How do I prove the following proposition? Let $T$ be a tree, and let $S$ be a subset of the vertices. If $|S|$ is even then we can partition $S$ into pairs $(x_i,y_i)$ such that the paths $x_i-y_i$ ...
1
vote
1answer
17 views

Proof the number of expected node in a binary using mathematical induction

The following algorithm constructs a binary tree. ...
1
vote
1answer
40 views

Height of AVL tree with balance condition of 2

The maximum height of an AVL tree with a balance condition of 1 is 1.44log(n). So the worst case height is O(logn). However, if the balance condition was hypothetically 2 (meaning that the allowed ...
0
votes
0answers
22 views

Trying to convert algorithm from recursive to iterative

I have this algorithm to sum binary tree branches from leftmost branch to rightmost one, so the solution is an array of sums: ...
0
votes
0answers
33 views

Number of weight-balanced nodes in binary tree

I have to show that a binary tree with $n$ nodes has at least $(n-1)/2$ weight-balanced nodes and at most $n-1$ weight-balanced nodes. Here a node is weight-balanced if its siblings satisfy $\...
0
votes
0answers
10 views

Complexity of a cutting operation on a list of binary trees

Consider a list of full binary trees of heights $(h_0, h_1, \ldots, h_{n-1})$ where a tree with a single leaf is deemed to have height 0. The list has the property that the height of the tree when ...
0
votes
0answers
22 views

Data structure for a queue of weighted elements

Consider a queue of elements with weights $w_0, w_1 \ldots, w_{n-1}$. The queue supports two operations: Inserting one element at the back of the queue Reducing the weight of one element in the ...
0
votes
0answers
15 views

Probability that BST has exact height

Consider keys $[ 1 \ldots n]$. We want to calculate probability that BST tree has height = $h$. (We assume that distribution is uniform over all $C_{n}$ trees, where $C_n$ - n-th Catalan number). ...
1
vote
1answer
242 views

What exactly is the difference between a Balanced Binary Search Tree and an AVL tree?

I'm learning some Data Structures and I cannot figure out the difference between the Balanced BST and the AVL Tree. From my understanding, an AVL tree is a balanced tree with the height difference <...
0
votes
1answer
30 views

Depth of binary tree with few single children

The node of a binary tree is called a single child if it has a parent but does not have a sibling. The root is by definition not considered a single child. Let $T$ be a binary tree of size $n$, and ...
0
votes
0answers
29 views

LOUDS Succinct Tree Representation

I am trying to make my Trie tree structure as compact as possible. While searching about this I came across to "Level order Unary Degree Sequence " i.e. LOUDS representations using bit ...
0
votes
0answers
21 views

Expected runtime for hashing with a binary search tree as collision handling

I thought about implementing a data structure with expected runtime of O(1) for insertion, deletion and look-up and a worst case runtime for these operations of O(log(n)). This is under the assumption ...
0
votes
2answers
28 views

Is the heap in “Data Structures Algorithms in Java” by Goodrich, Tamassia, and Goldwasser missing sentinel leaves?

In the book, Data Structures Algorithms in Java Sixth Edition by Goodrich, Tamassia, and Goldwasser on page 339, there is an "Example of a heap storing 13 entries with integer keys. The last ...
1
vote
1answer
27 views

Range sum query - tree representation efficiency

I was reading about possible solutions to the well known problem: Given array A with length N create a structure that enables ...
0
votes
0answers
35 views

(Searching + Splaying) in a Splay Tree

Given a tree To search for value 1, I do the following splay operations: i) Zag on 7 ii) Zag on 1 And hence obtain 1 in the root. But why would this be incorrect? i) Zag on 1 ii) Zag on 1 The ...
1
vote
1answer
361 views

Why does the formula floor((i-1)/2) find the parent node in a binary heap?

I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the index of the parent of element at index i can be found with parent ...
0
votes
1answer
63 views

How to draw the heap for an array in Java?

I have an assignment to draw the heap after an ArrayList and a LinkedList is created. ...
1
vote
1answer
30 views
5
votes
1answer
40 views

Test two LTL expression trees for equivalence

Is there an algorithm on how to check if two LTL expressions (represented as binary trees) are semantically equivalent? Since there are many smaller equivalences such as $a\Rightarrow b \equiv \neg a \...
6
votes
0answers
153 views

Impossibility of certain type of tree traversal algorithm

I was wondering for some time how to approach a situation like the following one. Imagine a standard binary tree data structure with $n$ nodes in it. Each node contains pointers to its left and right ...
5
votes
2answers
144 views

Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?

The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the ...
0
votes
1answer
26 views

Basic Binary search tree query

Inorder traversal of BST is always sorted.But can we say Binary tree is BST if and only if inorder is sorted?I mean if inorder is sorted,can we conclude it is always BST?
2
votes
0answers
23 views

How to linearly combine loss functions to preserve optimal substructure property?

I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has ...
0
votes
0answers
33 views

Simplify logical expression represented as binary tree

I implemented logical expressions using a binary tree in C++. Now I want to be able to simplify such an expression using rules like e.g. but have issues with the commutativity. Assuming the ...
1
vote
0answers
23 views

Recording a histogram in a tree exhibits strange best case

The task is to record a histogram from a streaming data source. One data point is, say, a 16 bit integer. The maximum multiple of one data point before the stream ends, is < 2^32. The main ...
2
votes
0answers
24 views

Data Structures for BST where size uniquely determines shape

There are several data structures in which the number of elements uniquely determines the shape. Examples would be binary heaps, arrays, lists, Braun trees, and Merkle mountain ranges. Are there any ...
0
votes
1answer
39 views

Range search in a max-heap

I am having trouble with coming up for a suitable algorithm for this question. A max-heap is essentially visualized as a binary tree not a binary search tree. Also the runtime of the algorithm must ...
0
votes
0answers
9 views

Why are these BVH split heuristic formulas different?

I've been doing some research into changing the split heuristic I use for a work project comprised of a BVH binary tree. The heuristic I currently use is centroid median as described here, but I seek ...
2
votes
1answer
121 views

Efficiently storing and modifying a reorderable data structure in a database

I'm trying to create a list curation web app. One thing that's important to me is being able to drag-and-drop reorder items in the list easily. At first I thought I could just store the order of each ...
1
vote
1answer
48 views

Best case “skew height” of an arbitrary tree

Given an arbitrary binary tree on $n$ nodes, choose an assignment $A$ from each parent to one of its children (the "favored child" as it were). We define the skew height of the tree as $H_A(\...
0
votes
1answer
3k views

What are the minimum and maximum numbers of elements in a heap of height h?

I came across the question: What are the minimum and maximum numbers of elements in a heap of height $h$? To which I came up with this theory: $$\sum_{i=0}^{h-1} 2^i = 2^h-1$$ $2^h-1$ is the ...
0
votes
0answers
20 views

Recurrence Relations for Perfect Quad Trees (same as binary trees but with 4 children instead of 2)

I have to write and solve a recurrence relation for n(d), showing how I arrive at the formula and solve the recurrence relation, showing how I arrive at the solution. Then prove my answer is correct ...
0
votes
1answer
38 views

Use tree in-order traversal to determine whether a BST or Heap

Given these in-order traversal lists: 1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19 2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17 I need to determine whether each one of those lists represent a valid BST ...
0
votes
1answer
45 views

Does the heap property in the definition of binary heaps apply recursively?

The definition of binary heaps says that it should be a complete binary tree and it should follow the heap property where according to the heap property, the key ...
1
vote
1answer
40 views

Product of all nodes except for one in Binary Tree

Assume we are given a binary tree with an integer sitting at each node. I am looking for an efficient way to find for every path from the root to a leaf every possible product with exactly one node ...
11
votes
6answers
1k views

Find the number using binary search against one possible lie

We all know this classic problem, "there is some hidden number and you have to interactively guess it.", which could be solved using binary search when we know that maximum number that we can guess. ...
0
votes
1answer
37 views

How many different (full/complete) in-order binary-trees do exist?

Given be a binary tree whose elements printed in-order results in [1,2,3,4]. Q1: How many different binary-trees do exist? Q2: How many different complete binary-...
1
vote
1answer
49 views

Can the structure of a “Complete Binary Tree”, be uniquely identified if only its pre-order or post-order or in-order traversals are given?

I am unable to reason if we can construct a complete binary tree if only one of the following 3 traversals is given: pre-order, post-order, in-order. The following is the definition of a complete ...
1
vote
1answer
39 views

Is there an Interval Tree which supports O(1) dynamic space requirements for queries?

I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key). In general ...
0
votes
1answer
135 views

Prove that AVL tree has this kind of property with Fibonacci sequence

Q: Prove that for any AVL tree that has $n$ nodes ($n\geq 1$) and has a height of $h$ this property is true: $n \geq F(h)$ where $F(h)$ is the $h$-th element in the Fibonacci sequence: $F(0) =0, F(1)=...
0
votes
0answers
12 views

Parsing text, then searching it: one entry per position, vs. 1 JSON column per text

I have a Rails application using Postgresql. Texts get added to the application (ranging in size -- as short as a few words, to as long as, say, 5,000 words?). The text gets parsed, both ...

1
2 3 4 5
10