Questions tagged [binary-trees]

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

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 123
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 315
-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.
user avatar
  • 99
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 &...
user avatar
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 ...
user avatar
  • 381
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 ...
user avatar
  • 187
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 : ...
user avatar
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 $...
user avatar
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 ...
user avatar
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, ...
user avatar
-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 ...
user avatar
  • 1
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 ...
user avatar
  • 215
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 ...
user avatar
  • 215
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 ...
user avatar
  • 121
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}{...
user avatar
  • 101
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 ...
user avatar
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? ...
user avatar
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 ...
user avatar
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}$ ...
user avatar
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: ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 915
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 ...
user avatar
  • 11
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.
user avatar
  • 13
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)
user avatar
  • 13
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 ...
user avatar
  • 11
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 ...
user avatar
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 ...
user avatar
  • 31
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; ...
user avatar
  • 140
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 ...
user avatar
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 ...
user avatar
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 ?
user avatar
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 ...
user avatar
  • 11
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 ...
user avatar
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 ...
user avatar
  • 111
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 117
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 ...
user avatar
  • 13
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: ...
user avatar
  • 123
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 ...
user avatar
-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 ?
user avatar
  • 1
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 ...
user avatar
  • 175
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 ...
user avatar
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.
user avatar
  • 113
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 ...
user avatar

1
2 3 4 5
11