0
$\begingroup$

I have some propositions regarding BSTs , please can someone confirm whether they are true or false:

Question :

1.Suppose we have a node $n_1$ with a value $val_1$ i.e $n_1(val_1)$

2.We wish to find the number of children of the predecessor node of $n_1$ , with respect to inline traversal (That is the number of children of node $n_2(val_2)$ with $val_2$ being the greatest number $val_2 < val_1$)

3.Assume for simplicity that the BST dosen't have any repetition

Proposition 1: Let $n_1$ have two children .Then $n_2$ has atmost one child i.e the number of children of $n_2$ can't be two

Proposition 2: Let $n_1$ have only one child and $n_1$ is not root ,then also $n_2$ has atmost one child.

Please ascertain whether these propositions are true , but if false can someone provide a counter example ?

$\endgroup$
2
  • $\begingroup$ We prefer that you ask only one question per post. Also, we'd like to see your thoughts and your attempt. I suggest you work through some examples and see if you can find a counterexample or formulate some idea at why you tink it might be true. $\endgroup$
    – D.W.
    Apr 23 '20 at 5:24
  • $\begingroup$ (Why would presence or absence of a successor node to $n_1$/a right child have any relevance to its left? You are not wrong in stating also.) $\endgroup$
    – greybeard
    Apr 23 '20 at 5:41
0
$\begingroup$

The Q is not clear enough for me, an in-order traversal will get u "n2" as the predecessor of "n1" so what is exactly required???

Regarding ur prepositions:

-P1: if n1 has 2 children, or just a left child, then n2 is the rightmost leaf of n1's left child

So Proposition 1 is correct

-P2:
-As stated above, if n1 only child is a left child, n2 have atmost only left child. (meaning not just at most 1, but it must be left)

-if n1 has only a right child, then reverse the argument; i.e., n2 is the node n1 is her left child of a right child (search upward for a node smaller than n1.. its parent if it is a right child does not make a difference if its parent has another left child or not, parent of parent,....)

For the bold case inside the brackets, ur second proposition is wrong.

I'll try to find an example picture, u may search any data structure text book for a complete tree to exhaust all different cases by ur self

Check the example in the second pic in this Q (My mobile is subject to a Denial of Service attack that prevents attaching it here again)

Ambiguity with the Top View of a binary tree

It is clear that 10 precedes 11, 11 has one right child while 10 has two enter image description here

$\endgroup$
2
  • $\begingroup$ I edited the question hope it is clear $\endgroup$ Apr 22 '20 at 16:22
  • $\begingroup$ Oh yes, I got it. Propestion1 is right, I think I explained why; I'll check 2. $\endgroup$
    – ShAr
    Apr 22 '20 at 17:27
0
$\begingroup$

They're both false. Simple counterexamples:

Proposition 1

  2
 / \
1   4
   / \
  3   5

n1 = 4
n2 = 2
number of children of n2 : 2
Proposition 2

  2
 / \
1   4
   /
  3  

n1 = 4
n2 = 2
number of children of n2 : 2

Note how the two counter-examples are almost identical. I only changed the number of children of n1 to satisfy your hypotheses; and it had no impact whatsoever on the number of children of n2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.