Any node in a binary or tree that does not have any children is known as a leaf node.

The top node in a tree is known as the root node.

How do you check if a given binary tree is a subtree of another binary tree?

Consider, we have a binary tree T, and we need to check if a binary tree S is a subtree of T. To do that, first, find a node in T that is also in S. Once you locate this common node, check if the following nodes are also part of S. If yes, we can say that S is a subtree of T.

How to find the distance b/w two nodes in a binary tree?

Consider nodes n1 and n2, which are part of a binary tree.The distance between the above two nodes is the same as the minimum number of edges that want to be traversed to reach from one node to the other.

Binary trees - Naukri Code 360

Introduction

A tree whose elements have at most two children is called a binary tree. Considering the fact that every element in a binary tree can have only two children, we commonly name them the left and right child.

A Binary Tree node contains data, a pointer to the left child, and a pointer to the right child.

Questions

1. Consider an entire binary tree with 7 nodes. Let A denote the set of the first three elements obtained by acting Breadth-First search (BFS) starting from the root. Let B denote the set of the first three elements obtained by appearing depth-First search (DFS) starting from the root. The value of ∣A−B∣ is ___________.

(A) 1

(B) 2

(D) 4

Solution: (A) 1

In the case of BFS, if we draw an entire binary tree, then in Set A, we have level1 + level2.

In DFS we have level1+ level 2 + level 3.

So A-B= remaining element of level 2.

2. What will be the worst-case number of arithmetic operations finished by recursive binary search on a sorted array of length n?

(A) Θ(√n)

(B) Θ(log2(n))

(D) Θ(n)

Solution: (B) Θ(log2(n))

Arithmetic operations carried out by binary search on sorted data items means the computation of mid element required arithmetic operation. So it will likely be computed log(n) time.

3. What is the worst-case time complexity of initially placing n² elements into an AVL tree with n elements?

(A) Θ(n⁴)

(B) Θ(n²)

(D) Θ(n³)

Solution: (C) Θ(n² log n)

1st insertion time complexity = O(log n)

2nd insertion time complexity = O(log(n+1))

3rd insertion time complexity = O(log(n+2))

n²th insertion time complexity = O(log(n + n²))

So, time complexity will be,

= O(log n) + O(log n+1)) + .... + O(log(n + n²))

= O(log n*(n+1)*(n+2)*...(n+n²))

= O(log nn²)

= O(n² log n)

4. A binary search tree wherein each non-leaf node has non-empty left, and right subtrees is a strictly binary tree. Any such tree with 19 leaves:

(A) cannot have more than 37 nodes

(B) has exactly 37 nodes

(D) cannot have more than 35 nodes

Solution: (B) has exactly 37 nodes.

(2n-1) where n is the for the leaves nodes. So by that way, we've exactly 37 nodes.

5. A full binary tree having n leaves contains

(A) log 2n nodes

(B) n nodes

(D) 2n nodes

Solution: (C) 2n-1 node

A full binary tree node has 0 or 2 children. We can say that a full binary tree is a binary tree in which all nodes except leaves have children. A full binary tree with n leaves consists of 2n – 1 node.

6. A complete binary tree with the property that the value at every node is as least as large as the values at its children is called

(A) binary search tree

(B) AVL tree

(D) Heap

Solution: (D) Heap

In a Max. Binary Heap, the key-value at every node is as least as big as the values at its children. Further in Min Binary Heap, the key at root should be minimum among all keys present in Binary Heap.

7. Which of the following various nodes can form a full binary tree?

(A) 8

(B) 15

(D) 13

Solution: (B) 15

A binary tree in which nodes except leaves have children is known as a complete binary tree.

In a complete Binary, the number of leaf nodes is the number of internal nodes + 1.

8. The order of a leaf node in a B+ tree is the maximum number of children it can have. Suppose that block size is 1 kilobyte, the child pointer is 7 bytes long, and the search field value takes 14 bytes long. The order of the leaf node is ________.

(A) 16

(B) 63

(D) 68

Solution: (A) 16

Given:

Key size = 14 bytes

Child pointer = 7 bytes

We assume the order of the B+ tree to be 'n'.

Block size >= (n - 1) * key size + n * child pointer

512 >= (n - 1) * 14 + n * 7

512 >= 14 * n - 14 + 7 * n

n <= (1024 + 14) / 20

n <= 1038 / 21

n <= 49.42

9. A strictly binary tree with 10 leaves

(A) cannot have more than 19 nodes

(B) has exactly 19 nodes

(D) has exactly 20 nodes

Solution: (B) has exactly 19 nodes.

A strict binary tree with n(i.e., 10) leaf nodes constantly has 2n-1(i.e., 19) intermediate nodes.

10. The range of structurally different possible binary trees with 4 nodes is

(A) 14

(B) 12

(D) 168

Solution: (A) 14

The total number of structurally different possible binary trees can be found using the Catalon number, which is (2n)!/ (n! *(n+1)!).

Now, n=4 implies the solution is 14.

11. In a binary tree, the number of internal nodes of degree 1 is five, and the wide variety of inner nodes of degree 2 is 10. The variety of leaf nodes inside the binary tree is

(A) 10

(B) 11

(D) 15

Solution: (B) 11

In a binary tree, the number of leaf nodes is continually 1 more than the number of internal nodes with 2 children.

So,

number of Leaf Nodes = number of internal nodes with 2 children + 1

number of Leaf Nodes = 10 + 1

number of Leaf Nodes = 11

12. Consider a node in a Binary Tree. Given that X has two children permit Y to be Inorder successor of X. Which of the following is true about Y?

(A) Y has no right child

(B) Y has no left child

(D) None of the above

Solution: (B) Y has no left child

Since X has both children, Y needs to be the leftmost node in the right child of X.

13. In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its descendant. What's the range of nodes inside the tree which have exactly one child?

(A) 0

(B) 1

(D) n-1

Solution: (A) 0

It is cited that every node has an odd number of descendants, including the node itself, so all nodes must have an even number of descendants 0, 2, 4 so on. this means that every node needs to have either zero or 2 children. So there can be no node with 1 child. Subsequently, 0 is a solution.

14. The height of a tree is the length of the longest root-to-leaf path. The maximum and minimum number of nodes in a binary tree of height 5 is

(A) 63 and 6, respectively

(B) 64 and 5, respectively

(D) 31 and 5, respectively

Solution: (A) 63 and 6, respectively

The number of nodes is maximum for a perfect binary tree.

A perfect binary tree of height h has 2^h+1 - 1 node.

The number of nodes is minimum for a skewed binary tree.

A perfect binary tree of height h has h+1 nodes.

Must Read Recursive Binary Search.

FAQs

What is a leaf node?
Any node in a binary or tree that does not have any children is known as a leaf node.
What is a root node?
The top node in a tree is known as the root node.
How do you check if a given binary tree is a subtree of another binary tree?
Consider, we have a binary tree T, and we need to check if a binary tree S is a subtree of T. To do that, first, find a node in T that is also in S. Once you locate this common node, check if the following nodes are also part of S. If yes, we can say that S is a subtree of T.
How to find the distance b/w two nodes in a binary tree?
Consider nodes n1 and n2, which are part of a binary tree.
The distance between the above two nodes is the same as the minimum number of edges that want to be traversed to reach from one node to the other.

Key Takeaways

In this article, we have discussed binary trees from previous year's questions. We hope that this blog will help you understand the questions based on binary trees that come in competitive GATE exams and if you would like to learn more about the binary tree, check out our other articles on Binary tree.

Binary trees