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
0answers
5 views

find a general case for DFS with O(1) space complexity

I found an interesting O(1) space complexity solution for DFS in a full binary tree where path information is not required. I need your help to find the general ...
0
votes
0answers
27 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
2answers
59 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
1answer
12 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
0answers
26 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
0answers
55 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
1answer
21 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
1answer
32 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
0answers
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
1answer
27 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
1answer
30 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 ...
1
vote
1answer
65 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
1answer
65 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
2answers
58 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
1answer
38 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
1answer
49 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
2answers
80 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
0answers
143 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
2answers
110 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
1answer
57 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
1answer
56 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
1answer
29 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
1answer
26 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
1answer
36 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
1answer
27 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
1answer
52 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
1answer
62 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 ...
0
votes
0answers
19 views

Time analysis of $m$ search operation in a Splay tree of nodes who have subtrees of size at least $\frac{n}{\log n}$

I know that the Worst-case for $m$ search operations in a Splay-tree is $O(m\log n +n \log n)$ The thing I'm not sure of is how this runtime depends on the size of the subtrees of the searched nodes. ...
-1
votes
1answer
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
1answer
66 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
0answers
13 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
1answer
42 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
0answers
37 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 ...
3
votes
0answers
122 views

How to find the Expected height of a randomly built binary tree

I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
0
votes
0answers
29 views

Order-statistic tree: Worst-case running time of a sequence of $n$ insertions/deletions and $m$ calls to SELECT operation

Assume I have an order-statistic tree, $T$, which is a red-black tree where every node $x$ also has the attribute $x.size$. How can I compute the worst-case running time of an arbitrary sequence of $n$...
0
votes
2answers
69 views

Assigning keys to the nodes of a Binary search tree given its shape

Let's say I have a Binary search tree with $n$ nodes and know its shape. I also knows each node has a unique key that is an integer between $1$ and $n$ (inclusive). This would make the assignment of ...
0
votes
1answer
34 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
vote
3answers
109 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
27 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
35 views

Difference between Recursion Tree & Binary Tree

What's the difference? is a Recursion tree private case of Binary tree?
3
votes
3answers
373 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
355 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
23 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
23 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
19 views

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

The following algorithm constructs a binary tree. ...
1
vote
1answer
55 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
36 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
30 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
603 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
44 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 ...

1
2 3 4 5
11