2
$\begingroup$

Let's assume that we have a binary search tree with node Y that hasn't a right child and for whom a successor exists in the tree.

I want to prove that if I insert a node X into the tree and node X is greater than node Y and less than the successor of node Y then X will be added as the right child of Y.

Intuitively, this makes sense to me but my question is how do we prove this formally?

$\endgroup$

2 Answers 2

1
$\begingroup$

Due to the lack of definitions in the question, let us pick up a couple of definitions that are needed for a formal proof.

A binary rooted tree is a BST if its nodes are visited in its natural order by the inorder traversal. Inserting a new node into a BST means adding a new edge so that the new node becomes the child of some old node and the tree remains a BST.


Let us prove a useful lemma.
(Uniqueness of insertion into BST) Let $T$ be a BST. Let node $X$ be a new node that is not equal to any node in $T$. Then there exists a unique way to insert $X$ into $T$ so that $T$ remains a BST with the same root, where the insertion must add one edge to $T$ (without modifying the existing edges).

Proof by mathematical induction on $n$, the number of vertices in $T$.

  • The base case when $n=1$. If the new node is less than the root node, it has to inserted as the left child of the root node; otherwise, it has to be inserted as the right child of the root node.
  • Assume the lemma is true for BST whose number of vertices is smaller than $n$. Suppose $T$ is a BST of $n$ vertices with node $R$ as its root node. Suppose $X$ is a new node that is not equal to any node of $T$. There are two cases.
    • $X$ is less than $R$. If $R$ has no left child, then $X$ has to be inserted as the left child of $R$. Otherwise, $R$'s left subtree is a BST (because of the recursive nature of the inorder traversal). $T$ has to be inserted into $R$'s left subtree. By induction hypothesis, there exists a unique way to insert $X$ into $R$'s left subtree.
    • $X$ is greater than $R$. Just switch every "left" to "right" in the above case.

Proof is done. As you have indicated, this is intuitively so obvious!


Now let us prove a proposition that is slightly more general than what you want to prove.
(Right child insertion) Let $T$ be a BST with node $Y$ that does not have a right child. Let node $X$ be a new node larger than $Y$ such that any node that is larger than $Y$, if exists, must be larger than $X$. Then node $X$, if inserted, will be inserted as the right child of $Y$.

Proof. Let $T'$ be the binary tree obtained from $T$ when $X$ is added as the right child of $Y$. Compare the inorder traversal on $T$ and that on $T'$. By the definition of inorder traversal, the difference between them can happen only when each traverses the subtree rooted at $Y$.

Both traversals will visit the same left subtree of $Y$ first. Then both will visit $Y$. When it is time to visit the right subtree of $Y$, the former traversal has nothing to do since $Y$ has no right child in $T$ while the latter traversal will visit one more node, $X$ since $Y$ has $X$ as its right child in $T'$.

Since the nodes in $T$ is visited in its natural order by the former traversal, the nodes in $T'$ is visited in its natural order by the latter traversal as $X$ is the very next node that is larger than $Y$. By definition, $T'$ is a BST. According to the above uniqueness lemma, $X$ must be inserted as the right child of $Y$. Q.E.D.

$\endgroup$
0
$\begingroup$

Maybe this is not the "proof" you're looking for, but here's an attempt to convince anyone that $X$ will be inserted in the binary-search tree (BST) as $Y$'s right child.

The "proof" relies on the binary-search tree property and on the definition and correctness of the "insertion" and "successor" functions of a BST.

You start with the definition of a successor of a node $y$ in a BST:

  1. If a node $y$ has a right subtree, then the successor of $y$, call it $z$, is the minimum node of that right subtree

  2. Otherwise, it is the first ancestor of $y$, lets call it $z$, such that $y$ falls in the left subtree of $z$.

  3. If $z$ is not found in the previous two points, then $z$ does not exist, which implies that $y$ is the greatest element in the BST.

However, we also need to look at the pseudocode of the insertion function.

function insertion(T, x):
    // T is the binary-search tree
    // x is the element which needs to inserted in T
    if is_empty(T):
        T.root = x
    else:
        c = T.root  // c is the current node.
        p = c.parent  // p is the parent of c

        while is_not_null(c):
            p = c
            if x < c:
                c = c.left
            else:
                c = c.right
        if x < p:
            p.left = x
        else:
            p.right = x
        x.parent = p

Since, in your case, we know that $T$ is not empty, then the else block will be always executed in any run of the insertion algorithm. In the while loop, we go down the tree, until we find a node that is null (and c represents this null node). However, note that we keep track of the parent of that null node c, i.e. p. We know that p is going to be the parent of x, but we still do not know if x needs to be the left or right child of p, given that x could either be respectively smaller or greater than p. Once that is determined, using the if-else block after the while loop, we can also set the parent of x to be p.

I will not prove that this insertion algorithm is correct, that is, it maintains the BST property. We assume it is correct. Here's the "proof" then.

We know that $Y$ does not have a right child, but it has a successor. Therefore, the successor must be the first ancestor of $Y$, call it $Z$, such that $Y$ falls in the left subtree of $Z$. We know that $Z$ exists (by assumption). If you insert $X$ in the binary-search tree $T$, such that $Y < X < Z$, then $X$ will be the next successor of $Y$ (by definition).

Given that $Y < X < Z$, at some point during the insertion algorithm, the condition x < c is false (because $X > Y$), where c is $Y$ and x is $X$. This must be true because there is no node between $Y$ and $X$ in the tree. Hence, in that case, $X$ will consequently be inserted in the tree as $Y$'s right child.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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