search
Log In

Recent questions tagged trees

0 votes
1 answer
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)$
asked Mar 30 in DS Lakshman Patel RJIT 47 views
0 votes
4 answers
2
Any decision tree that sorts $n$ elements has height $\Omega (\lg n)$ $\Omega ( n)$ $\Omega (n \lg n)$ $\Omega ( n^{2})$
asked Mar 24 in Algorithms jothee 102 views
3 votes
3 answers
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$
asked Jan 13 in DS Satbir 560 views
1 vote
1 answer
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.
asked Nov 20, 2019 in Algorithms Kushagra गुप्ता 294 views
5 votes
3 answers
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$
asked Sep 13, 2019 in DS gatecse 238 views
2 votes
4 answers
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?
asked Jan 16, 2019 in DS sripo 1.1k views
0 votes
0 answers
7
For range queries every B+ tree index requires less I/O than a full table scan. can anyone explain?
asked Jan 2, 2019 in Databases newdreamz a1-z0 74 views
0 votes
0 answers
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
asked Dec 29, 2018 in DS jatin khachane 1 135 views
8 votes
2 answers
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)
asked Dec 27, 2018 in DS Ruturaj Mohanty 403 views
0 votes
2 answers
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?
asked Dec 25, 2018 in DS sripo 737 views
0 votes
0 answers
11
1 vote
1 answer
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.
asked Sep 18, 2018 in DS jothee 239 views
0 votes
0 answers
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
asked Sep 18, 2018 in Graph Theory Sandy Sharma 108 views
1 vote
1 answer
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.
asked Sep 18, 2018 in Graph Theory Sandy Sharma 215 views
0 votes
1 answer
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
asked Sep 18, 2018 in Graph Theory Sandy Sharma 276 views
0 votes
0 answers
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
asked Sep 18, 2018 in Graph Theory Sandy Sharma 91 views
2 votes
1 answer
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
asked Sep 18, 2018 in Graph Theory Sandy Sharma 124 views
1 vote
1 answer
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
asked Aug 4, 2018 in DS manvi_agarwal 177 views
1 vote
2 answers
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 ________.
asked Jul 27, 2018 in DS Sambhrant Maurya 271 views
0 votes
2 answers
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
asked Jul 13, 2018 in DS Pooja Khatri 2.7k views
0 votes
0 answers
23
How many total Homeomorphically Irreducible Trees are possible with 'n' nodes ?
asked Apr 11, 2018 in Graph Theory ankitgupta.1729 469 views
0 votes
2 answers
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, -, *, +
asked Mar 2, 2018 in Unknown Category gatecse 156 views
0 votes
1 answer
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 ?
asked Mar 1, 2018 in Algorithms Mathews George 156 views
0 votes
0 answers
26
True / False:- 1. : The difference between the number of nodes in a binary tree that have exactly two children and the number of leaf nodes is 1 2. Deletion of root of AVL tree will take O(n) time so that, resulted tree also have property of AVL tree. I think first is false ... in second it is correct as we can do in logn so o(n) is also correct. Given answer is : 1 is true and second is false.
asked Dec 7, 2017 in DS rahul sharma 5 171 views
1 vote
1 answer
27
$\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
asked Dec 7, 2017 in Databases Pawan Kumar 2 233 views
0 votes
2 answers
28
assume the preorder tŕaversal of binary tree is "abc" how many total different binary trees are possible whose postorder traversal.is "cba" with the given preorder traversal.?? how to find it ?
asked Dec 7, 2017 in Programming aaru14 348 views
...