Level order traversal of a rooted tree can be done by starting from the root and performing
Level order traversal of rooted tree can be done by starting from root and visiting all node at k level before visiting any node at k + 1 level, which is nothing but breadth first search.
The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a maxHeap. The resultant maxHeap is
Input sequence 32,15, 20, 30,12, 25,16 If i is the root then A [i] > A [2i] for 1 < i < n/2 and A [i] > A [2i + 1] for 1 < i < n/2 where 2i is the left of i and 2i + 1 is the right of i of a max heap.
Which one of the following binary trees has its inorder and preorder traversals as BCAD and ABCD, respectively?
Inorder traversal is BCAD and preorder traversal is ABCD.
The numbers 1 , 2 .... n are inserted in a binary search tree in some order, In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be
Number 1 ,2 , 3, ....... n are inserted into BST in some order.
Since we know total nodes = n
So, Left (root) + 1 + p = n
Left (root) = n - p - 1
Left (root) = n - (p + 1)
So, root element will be = left element + 1
= n - (p + 1) + 1
= n - p - 1 + 1
= n - p
A binary search tree contains the numbers 1,2, 3, 4, 5, 6, 7, 8, When the tree is traversed in preorder and the values in each node printed out, the sequence of values obtained is 5, 3,1, 2, 4, 6, 8, 7. If the tree is traversed in postorder, the sequence obtained would be
How many distinct binary search trees can be created out of 4 distinct keys?
Total number of distinct binary search tree with n nodes (key)
In a complete k-ary, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is
In a complete-k-ary tree. If every internal node has exacity k children then (k - 1) key contains no leaves, if there are n internal nodes, then number of leaves is n(k- 1) + 1.
In a binary max heap containing.n numbers, the smallest element can be found in time
MAX Heap used to identity max element in O(1) time for to identity min element require O(n), to apply the linear search.
In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is
Let number of vertices in binary tree = n Number of edges = n - 1
So, n - 1 = 1 x 5 + 2 x 10
n - 1 = 5 + 20
n = 26
Num ber of leaf nodes = 26 - 5 - 10 = 11
The inorder and preorder traversal of a binary tree are “dbeafcg" and “abdecfg’’ respectively. The postorder traversal of the binary tree is
The in order traversal sequence is dbeafcg and the pre order traversal sequence is abdecfg.
So the tree is
In the post order traversal the sequence is debfgca.
Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is
After inserting an element at leaf in max heap we perform binary search on the path from the new leaf to the root to find the correct position for the newly inserted element. Comparisions will take θ(loglogn) but time will be θ(logn) because of swap operations.
How many distinct BSTs can be constructed with 3 distinct keys?
For distinct BST we apply this formula
n = 3 here so C(6, 3) = 20 and 20/4 = 5
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
Maximum height of any AVL-tree with 7.
(There may be different way to draw AVL with 7 nodes).
A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?
We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?