Questions tagged [binary-trees]
a rooted tree in which each node has no more than two children
518
questions
2
votes
2
answers
78
views
Are reversed reverse preorder traversals equivalent to a postorder traversal?
I was viewing the solutions of other Leetcode users for the classic "post-order traversal of a binary tree" question, when to my surprise, I found a ton of users simply finding the reverse ...
2
votes
3
answers
108
views
Find the smallest difference between two numbers in a DS in O(1) time
I got an assignment to create a new data structure, with the following rules:
Init - O(1).
Insert x - O(log$_2$n).
Delete x - O(log$_2$n).
Search for x- O(log$_2$n).
Find max difference between two ...
2
votes
2
answers
602
views
An α-good tree with n nodes has height O(log n)
Let $α \in [0, 1)$ be a constant. For a rooted binary tree $T$ and a node $x$ in $T$, we denote by
$|x|$ the number of nodes in the subtree of $T$ rooted at $x$ (if $x$ = $NIL$ then $|x|$ = $0$). We
...
1
vote
2
answers
53
views
Why is a recurrence of $2N_{h-2}$ equal to $2^{h/2}$?
I was watching video 7. Binary Trees, Part 2: AVL, where professor Erik Demaine stated that $$2N_{h-2} = 2^{h/2\text{ (or maybe with floor or something... maybe it's ceiling)}}$$ where $N$ stands for ...
1
vote
0
answers
44
views
Breadth-first search (BFS) for binary tree
It is pretty simple to implement a DFS algorithm for a binary tree but what about BFS for binary trees? I tried to adapt the BFS algorithm for ordered tree, this is the result:
I presume that better ...
-1
votes
0
answers
25
views
What are the application of post-, pre-, in-order traversal of binary search tree?
What are the application of post-, pre-, in-order traversal of binary search tree? What are the practical industrial use cases for that? TIA.
1
vote
1
answer
38
views
prove an inequality on binary tree
Let $\mathcal{T}_n$ be the set of ordered binary trees that have n leaves.
$d_T(v)$ means the node $v$'s depth in the tree T.
Prove: for any $T\in \mathcal{T}_n$ , for any $\{c_1,c_2,...c_n\}$ , $c_i &...
2
votes
3
answers
1k
views
Is there a reason Depth-First Search and Breadth-First search commonly called "Search" instead of "Traversal?"
From my understanding, two separate and distinct operations can be performed on binary search trees: Search and Traversal.
Search: Given a key, search will run an algorithm to find the node containing ...
3
votes
1
answer
112
views
Using pre-,post-, and in-order indexes to find information about a Binary Search Tree
Recently I have been studying ways of traversing a BST (in python), and have collided with the terms pre-order, post-order and in-order.
I believe that I understood the three terms pretty well, and ...
3
votes
1
answer
429
views
Efficient data structure for insertion, deletion and smallest-not-in-range query on an array of integers
I'm trying to make a data structure $A$ that has the following features:
insert($a$) operation : insert given integer $a$ to $A$. It is assured that all integers are unique.
delete($b$) operation : ...
3
votes
1
answer
86
views
finding an algorithm for creating a priority search tree in linear time with presorting
A priority search tree is a binary tree satisfying the following:
every node $u$ stores a point $p_u = (x_u,y_u)$
every nonleaf $u$ stores an x-coordinate $x_u'$ called the split-line coordinate.
If $...
0
votes
0
answers
32
views
Transform binary tree to max heap with minimal number of key changes
I am stuck on this interview practice problem and could use some advice. Given a binary tree, assume that you are only allowed to change the values of the keys of the nodes so that the Max Heap ...
1
vote
1
answer
58
views
When is a max heap tree invariant under a root removal, followed by a re-insertion of the root?
Let $T$ be a max heap tree with no duplicate values amongst the nodes. When does $T$ satisfy the following.
Remove the root, and restructure the tree to satisfy the heap property.
Reinsert the root, ...
-1
votes
1
answer
38
views
Prove that f(T) = Ω(l log l) for any l-leaf binary tree T
I want to prove this:
For any binary tree T, let f(T) denote the sum of the depths of all
of the leaves of T. (The root is at depth 0, the children of the root are at depth 1, the
grandchildren of the ...
0
votes
0
answers
31
views
Upper bound of sum of sub-tree depth difference on a complete binary tree with $n$ leaves
A complete binary tree with $n$ leaves has $n-1$ internal nodes. For every internal node $i$, I care about the difference between the maximum depth of the left sub-tree and the maximum depth of the ...
0
votes
1
answer
72
views
Bound the sum of leaf depth on a complete binary tree of $n$ leaves
A complete binary tree is defined as a tree where each node has either 2 or 0 children.
For a complete binary tree with $n$ leaves, there can be different arrangements of nodes, let's define the ...
2
votes
0
answers
34
views
upper bound on the smallest modulus for perfect hashing of a Huffman tree
Given a full binary tree with 256 leaves and depth <= 64,
let H be the set of Huffman codes described by the tree (using 0 to go left, and 1 to go right, where ...
0
votes
1
answer
34
views
Number of nodes of a binary tree at height $i$
It is well known that at height $i$ the number of nodes is bounded by $ \frac{n}{2^{i+1}} $, for example there are at most $n/2$ leafs.
Now, it makes sense only if we're taking $ \left\lceil \frac{n}{...
0
votes
1
answer
55
views
Solving a recurrence relation with two variables
I have this function which traverses each node of a left child-right sibling binary tree once and I want to solve the recurrence relation of the function.
First of all I think the relation looks like ...
0
votes
0
answers
64
views
Is there a difference between Heapify and Bottom-Up/Top-Down heap construction, when using array representation of binary tree?
Won't both the methods ultimately give a max/min heap? So if I am given a binary tree, as an array, and am asked to convert it to a max heap, can I just use the bottom up construction of the heap?
...
2
votes
2
answers
70
views
If both could be implemented with the other, what are the differences between priority queues and binary heaps?
I've red that a binary heap can be implemented using a priority queue. I've also red the opposite, that a priority queue can be implemented using a binary heap.
This seems strange to me as ...
0
votes
1
answer
13
views
Online binary tree creation via $a\to ax$ and $ab\to a(bx)$
I wish to construct a sequence of unlabeled binary trees $T_n$ satisfying the following properties:
$T_n$ has $n$ leaves
$T_n$ is well balanced (height $\lg n+O(1)$)
$T_n$ is obtained from $T_{n-1}$ ...
1
vote
0
answers
31
views
Parse algebraic expression into a list of operations
Given algebraic expression in a string, I want to split it into a list of operations for building a parallel binary tree. For example, I'm trying to convert expression such as:
...
0
votes
0
answers
58
views
Write functions that run in O(1) time
This Question can be found in the book: ODS: An Introduction (Chapter 6)
Suppose we are given a binary tree with pre-, post-, and in-order numbers assigned to the nodes. Show how these numbers can be ...
0
votes
1
answer
32
views
Are AVL&RB Trees without additional storage for balance information in each node feasible?
One advantage claimed for scapegoat trees over other balanced trees like AVL or red-black(RB trees - just mentioning AVL henceforth) is not needing to store additional balance information.
But can't ...
1
vote
1
answer
41
views
Do Adjacency Lists from Binary Trees go both ways?
From my reading and research it appears it's one way, however my lecturer states that it goes both ways in his examples.
Let me show you what i mean by this.
He claims that a binary tree built from a ...
0
votes
0
answers
27
views
Find balanced edge of a binary tree [duplicate]
What algorithm can be used to find a balanced edge in a binary tree? If we remove that particular edge, the tree is split up nearly equally.
Each tree will have at most $\lceil{(2n-1)/3}\rceil$ nodes.
0
votes
1
answer
33
views
Algorithm to find the saddle point in a Binary tree
How to find a saddle point in a binary tree. where saddle point is a node in a tree whose value = min(the node and all its ancestors) = max ( the node and all its descendants)
1
vote
1
answer
60
views
Splitting a binary tree into two halves
I am looking to prove the following:
Each binary tree with $n \ge 2$ nodes has an edge whose removal results in two trees, each having at most $\lceil (2n-1)/3 \rceil$ nodes.
I am not sure how to ...
2
votes
1
answer
93
views
How to join two Scapegoat Trees in O(log n) time?
I am working on some binary-search-tree research and was surprised to find no mention of an algorithm to join two Scapegoat Trees. This is where two trees $L$ and $R$ are joined to create a single ...
2
votes
1
answer
80
views
Why recording non-existent children in the pre-order traversal will differentiate different binary trees?
I have tried to solve and understand LeetCode question "297. Serialize and Deserialize Binary Tree", and after I read their solution I came up with a question that I will be glad If you can ...
0
votes
2
answers
63
views
Binary Tree as 2D array with variable length raws
Usually we use the tree data structure when we care about time complexity for ins/del/...
-In this special case problem, space saving is mandatory too that is 2 pointers for each node is unaffordable; ...
1
vote
1
answer
46
views
Applications of Complete Binary Tree?
Wondering what are the real word applications of the Complete binary trees or Almost complete binary trees where the the last level of the tree may not be complete and all nodes in the last level are ...
3
votes
1
answer
58
views
Observations about the structure of an optimal Binary Search Tree
My question is about part 15.5 in CLRS (third edition)*, on optimal binary search trees.
I am confused about the following sentences:
Consider any subtree of a binary search tree. It must contain ...
0
votes
2
answers
92
views
Kth largest element of a Min Heap of size K is always root element
Why the Kth largest element of a Min Heap of size K is always root element of the Min Heap ? How to prove this ?
1
vote
0
answers
148
views
Minimum required ancestor-descendant relationship of n nodes to build a binary tree out of
I have an algorithmic question. Suppose there is a ground truth binary tree of N nodes and there is an oracle which answers queries of the form: given any user specified pair of nodes a and b, do a ...
0
votes
3
answers
363
views
Is DFS better than BFS for space complexity when finding path from root to a node in a tree?
For simplicity, and I think without loss of generality, we can consider a binary tree. Suppose that we want to find the path between the root node and some node in the tree (we don't know where it is ...
1
vote
1
answer
89
views
More efficient way to parse array into binary search tree
Let's assume I have array which I need to parse into binary tree
...
0
votes
1
answer
147
views
When can a (max) heap be a BST?
Cheers, let's suppose we have a MAX heap which does not allow duplicate elements. Is it possible for this heap to be a BST ? Choose the right answer(s) below:
A heap can never be a BST
A heap is ...
0
votes
1
answer
40
views
Find two nodes in a BST such that the root's key is the average of their keys without extra space in $\theta(n)$ worst case time
We can do this in $\theta(n^2)$ time if we calculate the average of all couples of nodes in the tree and compare it to the root, but this is too much time.
We can do this in linear time but with extra ...
1
vote
1
answer
28
views
Is this a good way to arrange data in a tree?
I was recently learning about Binary Search Trees(BSTs) and thought it could be made even more efficient by making some changes.
As binary search trees have numbers greater than the root node on the ...
0
votes
1
answer
39
views
Checking two properties of a tree
I have the following definition:
A green-blue tree is a binary tree that follows the following properties:
Each green node has only blue descendants.
Every path that goes from a node to a leaf has ...
0
votes
1
answer
35
views
Converting Binary Search Tree into Decreasing Ordered Linked List
Given a BST with n nodes, the algorithm should create a linked list that contains a decreasing order sorted array. The algorithm should have a worst case time complexity O(n). The signature of the ...
1
vote
1
answer
56
views
If a key in a red-black tree has exactly one child (which isn't null) then it is always red
I have the following claim:
Prove or disprove: If a key in a red-black tree has exactly one child (which isn't null) then it is always red.
My attempt:
Disproof.
We will exhibit a counterexample:
...
0
votes
1
answer
69
views
Translating the in-order index of a node in a complete, balanced binary tree into the level-order index
Consider the topmost part of a complete, balanced binary tree of all 64-bit numbers, exemplified here.
As highlighted by the lack of a 7*2^64/8 term it is not ...
-1
votes
1
answer
41
views
Are there any trees where Preorder$(T_1) =$ Preorder$(T_2)$ and Inorder $(T_1) = $Inorder $(T_2)$, but $T_1 \neq T_2$?
Is it possible for two binary trees $T_1 \neq T_2$ that both Preorder and Inorder traversal are equal ?
1
vote
1
answer
85
views
How to prove the correctness of the binary tree inversion algorithm?
Define the inversion of a binary tree as the tree whose left sub-tree is a mirror reflection of the original tree's right sub-tree around the center and right sub-tree a mirror reflection of the ...
0
votes
0
answers
16
views
Can an LTL formula uniquely be represented by an expression tree?
Just like we can represent a mathematical expression uniquely with a binary expression tree, I was wondering if we could do the same for LTL formulae? Such that no two different looking LTL formula ...
0
votes
1
answer
47
views
Prove that in a tree where each node has 0 or 2 children, number of nodes with 0 child is one more than the number of nodes with 2 children
How to prove
In a tree where every node has either $0$ or $2$ children, the number of nodes with $0$ child is $1$ more than the number of nodes with $2$ children.
1
vote
0
answers
47
views
Weight of lowest common ancestor satisfies strong triangle inequality
How do I prove that $d(x,y)$, defined as the weight of the lowest common ancestor of $x,y$, satisfies the strong triangle inequality:
$$ d(x,y) \le \max(d(x,z), d(y,z)) $$
How do I even start such a ...