The Gateway to Computer Science Excellence
+4 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 by Boss (17.5k points)
recategorized by | 146 views

2 Answers

+1 vote



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.

by Boss (18.9k points)
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

by (17 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
104,898 users