# Finding the number of children of the predecessor node of a given node in a Binary Search Tree(BST)

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 ?

• 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.
– D.W.
Apr 23, 2020 at 5:24
• (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.) Apr 23, 2020 at 5:41

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 • I edited the question hope it is clear Apr 22, 2020 at 16:22
• Oh yes, I got it. Propestion1 is right, I think I explained why; I'll check 2.
– ShAr
Apr 22, 2020 at 17:27

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.

Let us consider the position of the inorder successor of a node in a binary tree. We need to consider two very symmetric cases

• The node has a right child. Then the successor is the first (in inorder) node of that right subtree. It is the most leftmost node, so succ itself has no left child.

• The node has no right child. Then the node is the last (in inorder) node of the left subtree of succ. Hence succ must have a left child.

The existence of a left child for node, and a right child for succ is unimportant. So it is very well possible that both node and its successor both have only a single child. Regarding the first proposition: Here $$n_1$$ is the successor of node $$n_2$$. If $$n_2$$ has two children, it has a right child, thus $$n_1$$ has no left child (left diagram).