# Tagged Questions

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

69 views

### Zero-based array implementation with logarithmic insertion time

Normal zero-based arrays (ie not those with a sort order) have constant lookup time, but linear insertion time. For a specific problem I was musing about a balanced tree that would allow for an zero-...
25 views

31 views

### Can minimum or maximum height of the binary search tree be constrained by the position of some elements

I came across one problem, which read as follows: We want to place the 13 letters A, B, C, D, E, F, G, H, I, J, K, L, M in a binary search tree with the minimum number of levels: 4. Because there ...
102 views

### How many number of different binary trees are possible for a given postorder (or preorder) traversal

I came across the problem: What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A,B,C? Now 3 being small number I was quick to draw all possible ...
42 views

### Keeping a binary search tree by splitting nodes (like a B-Tree)

A B-tree is kept balanced (i.e. all leaves at same depth) by splitting a node when adding a child that won't fit, and propagating this splitting up to the root. Can the same technique be used to keep ...
52 views

### Question on the properties of red black trees

Problem statement Let $T$ be a red black tree and $u$ some internal node of $T$. Suppose that in the left subtree of $u$ we have $n$ nodes. What is the maximum number of nodes that we can have in the ...
61 views

### Binary Search Tree Traversal output validity and unique BST construction

I had two specific type of questions involving Binary Search Tree (not simple Binary Tree) traversals : Given x-order traversal output of BST, can we state if it is valid or invalid output? (For ...
24 views

### Binary Indexed Tree(Fenwick Tree) - Range update and point Query

With the help of TopCoder Tutorial and this post, I was able to understand the basic idea of how basic the cumulative frequency sum is stored in the left subtree of a BIT node.I was successfully able ...
166 views

### Merging two binary heaps in linear time

Given two binary heaps, each represented by a binary tree with 2k-1 elements, design an algorithm to merge the two heaps into one heap in linear time. I've been having some difficulty in solving ...
101 views

### Is a balanced binary tree a complete binary tree?

Considering that the opposite is true it's not mentioned anything about this. I am assuming its not, but I need a very good distinction between these two types of binary trees. All I know is this: ...
50 views