# CMI2019-A-3

261 views

Suppose that the figure to the right is a binary search tree. The letters indicate the names of the nodes, not the values that are stored. What is the predecessor node, in terms of value, of the root node $A?$

1. $D$
2. $H$
3. $I$
4. $M$
in DS
recategorized
0
it is option C

$\underline{\mathbf{Answer:C}}$

$\underline{\mathbf{Explanation:}}$

For calculating $\color{green}{{\textbf{predecessor}}}$ and the $\color{green}{\textbf{successor}}$ we need to get the $\underline{\color{magenta}{\textbf{"inorder traversal"}}}$ of the binary tree.

$\color{magenta}{\underline{\textbf{Inorder traversal:}\Rightarrow}}$ $\color{blue}{\mathbf{DBHEM\color{red}{\bbox[orange, 3px, border:1px solid green]{I}}\color{black}{\enclose{circle}{\Large A}}\color{red}{\bbox[orange, 3px, border:1px solid green]{J}}FNKCLG}}$

In the result, which is obtained after getting inorder of the binary tree, the element which will come before the given node, $\mathbf{i.e.}\;\enclose{circle}{\mathbf {\color {magenta} I}}$ will be the predecessor and the element which will come afterwards will be the successor, $\mathbf{i.e.\;\enclose{circle} {\color {magenta} J}}$  will be the successor.

So, here $\color{red}{\mathbf{predecessor\; of\; A\; is\; \bbox[orange,5px, border:2px solid red]{\enclose{circle}{I}}}}$ and the $\color{green}{\mathbf{successor\;of\;A\; is\; \bbox[orange,5px, border:2px solid green]{\enclose{circle}{J}}}}$

$\therefore\mathbf C$ is the correct answer.

edited by

If Left subtree is not Null, then Inorder Predecessor is Rightmost node of left subtree.

Else lowest ancestor of that node where right child is also ancestor of that node is Inorder Predecessor.

According to this, here left subtree is not Null and rightmost node is I .

Option : C

Inorder traversal : $DBHEM----I----A-----J----FNKCLG$

A is the root $I$ is the inorder predecessor and $J$ is the inorder successor

## Related questions

Let us there are n nodes which are labelled. Then the number of trees possible is given by the Catalan Number i.e $\binom{2n}{n} / (n+1)$ Then the binary search trees possible is just 1?