# Questions tagged [binary-trees]

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

499 questions
Filter by
Sorted by
Tagged with
13 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 ...
20 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 ...
24 views

### Find balanced edge of a binary tree

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 $\ceil{(2n-1)/3}$
25 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)
26 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 ...
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 ...
53 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 ...
57 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; ...
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 ...
47 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 ...
78 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 ?
141 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 ...
72 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 ...
52 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 ...
42 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 ...
23 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 ...
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 ...
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 ...
25 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 ...
50 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: ...
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 ...
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. ...
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 ?
64 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 ...
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 ...
40 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.
36 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 ...
102 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 ...
28 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$...
59 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 ...
30 views

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 ...
29 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 ...
24 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). ...
563 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 <...
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 ...
25 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 ...