# Questions tagged [binary-trees]

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

518 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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
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
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 ...
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
38 views

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
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, ...
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 ...
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 ...
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 ...