# Recent questions tagged trees

1
In a complete $k$-ary tree, every internal node has exactly $k$ children. The number of leaves in such a tree with $n$ internal nodes is $nk$ $(n-1)k+1$ $n(k-1)+1$ $n(k-1)$
2
Any decision tree that sorts $n$ elements has height $\Omega (\lg n)$ $\Omega ( n)$ $\Omega (n \lg n)$ $\Omega ( n^{2})$
3
Of the following, which best approximates the ratio of the number of nonterminal nodes in the total number of nodes in a complete $K$-ary tree of depth $N$ ? $1/N$ $N-1/N$ $1/K$ $K-1/K$
1 vote
4
Argue that since sorting $n$ elements takes $\Omega (n\ lgn)$ time in the worst case in the comparison model, any comparison-based algorithm for constructing a $BST$ from an arbitrary list of n elements takes $\Omega (n\ lgn)$ time in the worst case.
5
Suppose that the figure to the right is a binary search tree. The letters indicate the names of the nodes, not the values that are stored. What is the predecessor node, in terms of value, of the root node $A?$ $D$ $H$ $I$ $M$
6
Let us there are n nodes which are labelled. Then the number of trees possible is given by the Catalan Number i.e $\binom{2n}{n} / (n+1)$ Then the binary search trees possible is just 1?
7
For range queries every B+ tree index requires less I/O than a full table scan. can anyone explain?
8
Leaf Nodes =[ Internal nodes with degree 2 ] + 1 It is valid if we consider Tree as undirected graph ? Or is it valid only for Tree when considered as directed graph
9
For a given $m$-ary tree, the relationship between leaf nodes and internal nodes is represented by the graph given below. What is the value of $'m'$? Take necessary approximations to nearest integer if required (Integer type)
10
In a 3-array tree if internal nodes have exactly 3 children,the number of leaf nodes will be __ ? Does it vary for binary tree? What do you mean by internal nodes? Non root node and leaf node?
11
1 vote
12
Consider the array $A=[20,13,19,8,3,5,4]$ that represents a heap. Draw the heap after removing the element $20.$ List all the distinct integer keys $k$ such that, when $k$ is inserted in the Binary Search Tree of Figure $1,$ its height increases. Note that you are not allowed to insert an already existing key again. Justify your answer.
13
Let T = (V, E) be a tree and let d(v) be the degree of a vertex. Consider following statements: (i) P v∈V (2 − d(v)) = 2 (ii) If T has a vertex of degree m ≥ 2, then it has at least m vertices of degree 1. (iii) P v∈V (k − d(v)) = k, for k ≥ 2 | k ∈ Z + Which of the above statements is/are ture: (A) (i) only (B) (i), (ii) only (C) (ii) and (iii) only (D) (i), (ii) and (iii) only
1 vote
14
For which of the following scenarios does there exist a simple graph G = (V, E) satisfying the specified conditions? (A) It has 3 components 20 vertices and 16 edges. (B) It has 10 vertices, 38 edges, and more than one component. (C) It has 7 vertices, 10 edges, and more than two components. (D) It is connected and has 10 edges 5 vertices and fewer than 6 cycles.
15
Consider following statements: (i) Every simple graph has at least two vertices of the same degree. (ii) If u is a vertex of odd degree in a graph, then there exists a path from u to another vertex v of the graph where v also has odd degree. (iii) If there are exactly two vertices a and ... the above statements are not true? (A) (i) and (ii) only (B) (iii) only (C) (ii) only (D) None of the above
16
Consider following statements about tripartite graph, i.e. TPG, which contains three subsets of vertices of graph as A,B and C: (i) Minimum number of edges in a cycle in a TPG which passes through all three subsets of vertices is 6. (ii) A complete TPG can be colored with atmost 3 colors. (iii) ... above statements are true: (A) (i) only (B) (iii) only (C) (ii) and (iii) only (D) (i) and (ii) only
17
A quinpartite graph is a graph whose vertices can be partitioned into five groups such that no two vertices in same group are connected via some edge. The maximum number of edges in a quinpartite graph with 10 vertices, where cardinalities of those five sets are given as {2,3,2,1,2}, is: (A) 16 (B) 20 (C) 26 (D) 39
18
1 vote
19
which is an efficient tree structure in terms of space and time complexity? a) AVL Tree b)Full Binary tree c)Complete binary tree d)Binary tree
1 vote
20
The number of binary search trees possible with 12 keys, when keys 1, 2, 3, 4, ........ 12 are inserted into empty Binary Search Tree with condition such that 4 is the root of binary search tree and 8 is immediate right child of 4 are ________.
21
A 5-ary tree in which every internal node has exactly 5 children. The number of left nodes in such a tree with 8 internal nodes will be: 30 33 45 125
22
23
How many total Homeomorphically Irreducible Trees are possible with 'n' nodes ?
24
If the post order traversal of tree gives $ab - cd * +$, then the label of the nodes A, B, C, ......, G will be a, -, b, +, c, *, d +, -, *, a, b, c, d -, a, +, b, c, d, * a, b, c, d, -, *, +
25
After deleting an element from a B-tree,I could rearrange the tree in several ways,that would still complies to the rules of B-trees.But,we are supposed to follow a certain set of rules for rearranging the tree after deleting an element. Why is that ?
$\text{Insertion Sequence}$ : $8,5,1,7,3,12,9,6$ Can someone plz show the Sequence of insertion in B+ tree step by step Thanks