Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Questions  >  A scheme for storing binary trees in an array... Start Learning for Free
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i 1]. To be able to store any binary tree on n vertices the minimum size of X should be.  

  • a) 
    log2n
  • b) 
    n
  • c) 
    2n + 1
  • d) 
    2^n — 1
Correct answer is option 'D'. Can you explain this answer?
Verified Answer
A scheme for storing binary trees in an array X is as follows. Indexin...
For a right skewed binary tree, number of nodes will be 2^n – 1. For example, in below binary tree, node ‘A’ will be stored at index 1, ‘B’ at index 3, ‘C’ at index 7 and ‘D’ at index 15.
View all questions of this test
Most Upvoted Answer
A scheme for storing binary trees in an array X is as follows. Indexin...
Explanation:

To store a binary tree on n vertices, we need an array X of size 2^n-1. This can be explained as follows:

Minimum number of nodes in a binary tree of height h is 2^h-1. For example, a binary tree of height 3 has minimum 2^3-1 = 7 nodes.

In a binary tree, the maximum number of nodes in the last level is 2^(h-1), where h is the height of the tree. For example, a binary tree of height 3 has maximum 2^(3-1) = 4 nodes in the last level.

To store any binary tree on n vertices, we need an array that can accommodate all the nodes of the tree. The number of nodes in a binary tree of height h is between 2^(h-1) and 2^h-1.

Therefore, the minimum size of X to store any binary tree on n vertices is 2^n-1.

Hence, option D (2^n-1) is the correct answer.
Free Test
Community Answer
A scheme for storing binary trees in an array X is as follows. Indexin...
We are asked for minimum size of 'x' then why should we take skewed tree.
If the question would have asked about the max size of X, then the answer should be D.
Explore Courses for Computer Science Engineering (CSE) exam

Similar Computer Science Engineering (CSE) Doubts

Top Courses for Computer Science Engineering (CSE)

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i 1]. To be able to store any binary tree on n vertices the minimum size of X should be.a)log2nb)nc)2n + 1d)2^n — 1Correct answer is option 'D'. Can you explain this answer?
Question Description
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i 1]. To be able to store any binary tree on n vertices the minimum size of X should be.a)log2nb)nc)2n + 1d)2^n — 1Correct answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i 1]. To be able to store any binary tree on n vertices the minimum size of X should be.a)log2nb)nc)2n + 1d)2^n — 1Correct answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i 1]. To be able to store any binary tree on n vertices the minimum size of X should be.a)log2nb)nc)2n + 1d)2^n — 1Correct answer is option 'D'. Can you explain this answer?.
Solutions for A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i 1]. To be able to store any binary tree on n vertices the minimum size of X should be.a)log2nb)nc)2n + 1d)2^n — 1Correct answer is option 'D'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i 1]. To be able to store any binary tree on n vertices the minimum size of X should be.a)log2nb)nc)2n + 1d)2^n — 1Correct answer is option 'D'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i 1]. To be able to store any binary tree on n vertices the minimum size of X should be.a)log2nb)nc)2n + 1d)2^n — 1Correct answer is option 'D'. Can you explain this answer?, a detailed solution for A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i 1]. To be able to store any binary tree on n vertices the minimum size of X should be.a)log2nb)nc)2n + 1d)2^n — 1Correct answer is option 'D'. Can you explain this answer? has been provided alongside types of A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i 1]. To be able to store any binary tree on n vertices the minimum size of X should be.a)log2nb)nc)2n + 1d)2^n — 1Correct answer is option 'D'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i 1]. To be able to store any binary tree on n vertices the minimum size of X should be.a)log2nb)nc)2n + 1d)2^n — 1Correct answer is option 'D'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Explore Courses
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev