Log In
5 votes

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 by
it is option C

3 Answers

2 votes



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
0 votes

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 . 

So, the correct answer is 

Option : C

0 votes
Answer will be (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

2 votes
4 answers
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?
asked Jan 16, 2019 in DS sripo 1.2k views