Which of the following cannot generate the full binary tree?a)Inorder ...
To generate a binary tree, two traversals are necessary and one of them must be inorder. But, a full binary tree can be generated from preorder and postorder traversals. Read the algorithm here. Read Can tree be constructed from given traversals?
View all questions of this test
Which of the following cannot generate the full binary tree?a)Inorder ...
Explanation:
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A full binary tree is a binary tree in which every node has either zero or two children.
Given three traversals of a binary tree, namely inorder, preorder and postorder, it is possible to reconstruct the binary tree. However, not all combinations of two traversals can be used to reconstruct the full binary tree.
a) Inorder and Preorder:
With inorder and preorder traversals, we can construct the tree uniquely. The first node in the preorder traversal is always the root of the tree. We can find this root in the inorder traversal, and all nodes to the left of the root in the inorder traversal are in the left subtree and all nodes to the right of the root in the inorder traversal are in the right subtree. We can then recursively construct the left and right subtrees using the remaining nodes in the preorder traversal.
b) Inorder and Postorder:
With inorder and postorder traversals, we can also construct the tree uniquely. The last node in the postorder traversal is always the root of the tree. We can find this root in the inorder traversal, and all nodes to the left of the root in the inorder traversal are in the left subtree and all nodes to the right of the root in the inorder traversal are in the right subtree. We can then recursively construct the left and right subtrees using the remaining nodes in the postorder traversal.
c) Preorder and Postorder:
With preorder and postorder traversals, it is not possible to construct the tree uniquely. This is because the first node in the preorder traversal is the root and the last node in the postorder traversal is also the root. However, we do not know which subtree comes first, the left or the right.
d) None of the above:
It is not possible to generate the full binary tree with none of the above combinations of traversals because every full binary tree can be reconstructed using either inorder and preorder or inorder and postorder traversals.