search
Log In

Recent questions tagged trees

4 votes
2 answers
1
An $articulation$ $point$ in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let $T$ be a $\text{DFS}$ tree obtained by doing $\text{DFS}$ in a connected undirected graph $G$. Which of the following ... and $y$ is a descendent of $u$ in $T$, then all paths from $x$ to $y$ in $G$ must pass through $u$.
asked Feb 18 in DS Arjun 2.5k views
0 votes
1 answer
2
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, 2020 in DS Lakshman Patel RJIT 274 views
0 votes
4 answers
3
Any decision tree that sorts $n$ elements has height $\Omega (\lg n)$ $\Omega ( n)$ $\Omega (n \lg n)$ $\Omega ( n^{2})$
asked Mar 24, 2020 in Algorithms jothee 281 views
4 votes
3 answers
4
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, 2020 in DS Satbir 1.1k views
1 vote
1 answer
5
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 गुप्ता 501 views
5 votes
4 answers
6
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 555 views
3 votes
4 answers
7
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 2.8k views
1 vote
0 answers
8
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 196 views
0 votes
0 answers
9
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 192 views
8 votes
2 answers
10
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 530 views
0 votes
2 answers
11
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 1.3k views
0 votes
3 answers
12
____ number of leaf nodes in a rooted tree of $n$ nodes, where each node is having $0$ or $3$ children $\frac{n}{2}$ $\frac{(2n+1)}{3}$ $\frac{(n-1)}{n}$ $(n-1)$
asked Dec 7, 2018 in DS Arjun 551 views
0 votes
0 answers
13
1 vote
1 answer
14
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 372 views
0 votes
0 answers
15
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 157 views
1 vote
1 answer
16
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 507 views
0 votes
1 answer
17
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 492 views
0 votes
0 answers
18
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 165 views
2 votes
1 answer
19
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 170 views
1 vote
1 answer
21
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 340 views
1 vote
2 answers
22
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 527 views
0 votes
2 answers
23
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 4.6k views
0 votes
0 answers
25
How many total Homeomorphically Irreducible Trees are possible with 'n' nodes ?
asked Apr 11, 2018 in Graph Theory ankitgupta.1729 862 views
0 votes
2 answers
26
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 218 views
...