Questions tagged [binary-trees]
a rooted tree in which each node has no more than two children
554
questions
1
vote
1
answer
57
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 ...
- 17
0
votes
0
answers
62
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
2
answers
61
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 ...
- 145
1
vote
1
answer
126
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
...
- 113
0
votes
0
answers
86
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 ...
- 101
3
votes
3
answers
10k
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 ...
- 49
0
votes
1
answer
307
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
0
votes
1
answer
117
views
5
votes
1
answer
166
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 \...
- 53
6
votes
0
answers
172
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 ...
- 61
4
votes
2
answers
275
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 ...
- 41
0
votes
1
answer
52
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?
- 431
2
votes
0
answers
27
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 ...
- 21
0
votes
0
answers
313
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 ...
- 13
1
vote
0
answers
29
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 ...
- 143
2
votes
0
answers
31
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
1
answer
384
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 ...
- 3
2
votes
1
answer
835
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 ...
- 21
1
vote
1
answer
118
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(\...
- 531
1
vote
2
answers
22k
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
1
answer
67
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 ...
- 167
0
votes
1
answer
146
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,215
1
vote
1
answer
85
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 ...
- 153
11
votes
6
answers
2k
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.
...
- 119
0
votes
1
answer
192
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-...
- 111
1
vote
1
answer
261
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 ...
- 161
0
votes
1
answer
127
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 ...
- 111
0
votes
1
answer
2k
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
0
answers
14
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 ...
- 101
1
vote
2
answers
135
views
check if a binary tree is a binary search tree
I have some doubts about this algorithm which checks if a binary tree is a binary search tree:
...
- 73
-1
votes
1
answer
58
views
checks if a tree is a full binary tree
I have to write an algorithm that checks if a tree is full binary tree (each node, except the leaves, must have 2 children), but I don't know if this version is correct.
...
- 73
1
vote
2
answers
238
views
Insert a node in a binary search tree
The teacher gave us this code that inserts a node in a binary search tree, but I am not sure what the $z.p = y$ instruction does. wouldn't the algorithm work without it?
...
- 73
1
vote
1
answer
142
views
Inorder Successor in Binary Search Tree
This is the problem that I have to solve:
given a node in a binary search tree, find the node
with the smallest key that is greater than the key of the given
node..
The algorithm that is ...
- 73
1
vote
2
answers
795
views
Deletion in a Binary search Tree
The teacher explained to us this algorithm for deleting a node in a binary search tree, but I can't understand how it works when the node to be deleted has only one child (I already know how it works ...
- 73
2
votes
2
answers
70
views
Ambiguity with the Top View of a binary tree
What exactly is the top view of a binary tree?
I find great ambiguity and lack of clarity from the articles I find.
For example, this is what is used to demonstrate the top view on geeksforgeeks:
<...
- 147
1
vote
3
answers
491
views
Finding the number of children of the predecessor node of a given node in a Binary Search Tree(BST)
I have some propositions regarding BSTs , please can someone confirm whether they are true or false:
Question :
1.Suppose we have a node $n_1$ with a value $val_1$ i.e $n_1(val_1)$
2.We wish ...
3
votes
2
answers
64
views
When should we construct trees, graphs to analyse an algorithm?
In many algorithms, it's easy to understand how the algorithm is executed, but as for why it works well and how it can work, it's not very easy to see, sometimes, authors construct trees or graphs to ...
- 145
0
votes
1
answer
700
views
Number of nodes of given height in binary heap
Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n$-element binary heap.
How can I show this? Or, how can I prove this?
0
votes
1
answer
139
views
binary code to encode binary tree
I would like to encode a binary tree where every node has either 0 or 2 kids into a binary word.
I was thinking about marking every left edge with a "0" and every right edge with a "1"
and then use ...
- 11
1
vote
2
answers
184
views
Is it necessary that Minimum/Maximum Heap must be a Binary Heap?
I find this extremely wrong, that a lot of books, articles, video tutorials, online courses or trainers define Minimum/Maximum Heap data structure as a particular type of the Binary Heap data ...
1
vote
0
answers
1k
views
Find the median element of two AVL trees in $O(\log n)$
I'm attempting the problem of finding the median element in two AVL BST's in $O(\log n)$ time. In this problem, we are given two AVLs, with a combined size of $n$ (the distribution across the two ...
- 11
1
vote
0
answers
29
views
Determining Range of Current Node in Segment Tree
I was attempting, though failing quite miserably, to find some method of of determining the range of some node $n$. By range I mean an interval $[l,r]$ over the base array that is reachable by the sub-...
- 111
1
vote
1
answer
538
views
Complexity of "Subtree of Another Tree"
I wrote an algorithm for a leetcode question. The question asks:
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A ...
- 141
0
votes
1
answer
763
views
Is there a faster than O(n^2) solution for Box stacking problem?
The Box Stacking problem is as follows:
You are given a set of $n$ types of rectangular 3-D boxes, where the
$i^{th}$ box has height $h_i$, width $w_i$ and depth $d_i$ (all real
numbers). You ...
- 17
0
votes
3
answers
365
views
How to convert a Complete Binary Tree to a Priority Search Tree in O(n)?
I would like to know if there is a linear-time algorithm ($\mathcal{O(n)}$ time) to convert a
Complete Binary Tree with data left-to-right increasing stored in
external nodes, to a Priority Search
...
- 13
1
vote
0
answers
17
views
Confusion with "every path from a given node to any of the leaves goes through the same number of black nodes" property of RB trees
One of the properties of Red Black trees is: "every path from a given node/vertex to any of the leaves goes through the same number of black nodes"
Two related questions about this property:
1) is ...
- 209
1
vote
1
answer
233
views
Performance of Recursive vs Iterative Solution to "Maximum Depth of a Binary Tree"
I am looking at this question from LeetCode.
There are two solutions to this question - the recursive solution and the iterative / breadth-first traversal solution.
My question is in regards to the ...
- 141
1
vote
1
answer
628
views
Efficiently finding the min-cost path of an AVL tree
It seems that in a full AVL tree, the left edge is always the minimum-cost path. For example, take the following full AVL tree:
The min-cost path would be 8-6-5. ...
- 111
2
votes
2
answers
7k
views
In a Binary Tree, can two nodes have the same value?
In a Binary Tree, can two nodes have the same value? For example:
3
/ \
4 4
/ \
1 2
They are two different nodes, but they have the same value....
- 151
3
votes
3
answers
1k
views
Can the same node appear twice in a tree?
Can the same node appear twice in a tree?
I'm asking about the node object itself, not the node's value. For example, in the following code, a's left and right ...
- 151