Consider a node X in a Binary Tree. Given that X has two children, let...
Since X has both children, Y must be leftmost node in right child of X.
View all questions of this test
Consider a node X in a Binary Tree. Given that X has two children, let...
Explanation:
In a binary tree, the inorder traversal of the tree follows the left subtree, then the root, and then the right subtree. Therefore, the inorder successor of a node X is the next node that would be visited in an inorder traversal of the tree.
If X has two children, then the inorder successor Y must be the leftmost node in X's right subtree. This is because all nodes in X's left subtree would come before X in an inorder traversal, and all nodes in X's right subtree would come after X, but before any nodes in X's parent's subtree.
Therefore, Y is the leftmost node in X's right subtree, which means that Y has no left child. If Y had a left child, that node would be even further to the left and would be the inorder successor of some other node in the tree.
Hence, the correct answer is option 'B': Y has no left child.
Consider a node X in a Binary Tree. Given that X has two children, let...
If Y has left child then the inorder traversal would be X (leftChildOfY) Y (rightChildOfY)