Binary Subtree and Count of Nodes Given two non-empty binary | Cse interview questions

Binary Subtree and Count of Nodes

Given two non-empty binary trees, check if the either tree is a subtree of the other one. Also print the count of nodes in that subtree.

A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T.

Examples :

Input 1 :

4
/ \
2 5
/ \
1 3

2
/ \
1 3

Output 1 :

true
3

Explanation 1 :

Here we can see that the internal node corresponding to value 2 of first tree and all its descendents, matches the second tree. So, second tree is a subtree to the first tree. Hence output true.

Also, number of nodes of subtree (second tree) is 3 which have values 2, 1 and 3.

Input 2 :

4
\
9

2
/ \
4 5

Output 2 :

false

Explanation 2 :

The only common node among the two trees is the node corresponding to value 4. But first tree has right child with value 9 while the second tree has no descendants. The criteria for subtree is not satisfied. So, here neither is the subtree of the other.

Since there is no subtree here, we don't output number of nodes of subtree. (Other possibilities like outputting null can be valid too, this can be discussed with the interviewer.)

Topic : Trees

Reference(s) -> GeeksforGeeks, LeetCode

Solution ->

for Binary Subtree,
refer GFG set 1, set 2

for Count of Nodes,
GFG article 1, article 2, Sanfoundry

Asked in Paytm

Join our Official Channel @cseinterview