Could anyone familliarize me with the proper way to approach a mathematical proof (Induction \ Recursion) regarding BST?
BST = Binary Search tree, where each node is: Greater than all of the values in his left subtree, Smaller than all the values in his right subtree. And each subtree in a BST is also a BST.
https://en.wikipedia.org/wiki/Binary_search_tree#Verification
I know how to do it in code but would like to write it as a proof.
I guess the base case for the induction\ recursion would be the same:
Range of the current root's value: x in(-inf,+inf) Range of the next left root: y in (-inf,x) Range of the next right root: z in (x,+inf)
But what is the PROPER way to Prove that it actually produces a BST Tree check?
EDIT: Summary of what I currently pursued:
Induction on N : number of nodes which aren't leaves in a BST Assuming: (Min,Max) : Range of node X Base case: N = 0 -> Empty BST Tree OR BST Tree with only one node X : X is in (-inf,+inf) N = 1 -> BST Tree with one node which is not a leaf: X in (-inf,+inf) BST -> Left 'son' Y : Y < X -> Y in (-inf,x) BST -> Right 'son' Z: Z > X -> Z in (x,+inf) (If either or both sons exist)
Induction: Assuming BST with N nodes which aren't leaves X = {X1,X2....XN} For all x in X : x in (min,max) -> y in (min,x) and z in (x,max)
Induction step: Taking a N + 1 nodes which aren't leaves BST: (Now what I'm conteplating about): Removing one node which has up to two descendats (At height H - 1)
Therefore two possible options:
1). Now it's a BST with N Nodes which arent leaves -> Induction assumption proves the verification works -> Adding it back and it still works 2). Now it's a BST with N - 1 Nodes which arent leaves (Because the node we removed was it's parent's only son, so we removed 2 of such nodes)
---That's where I'm stuck, I don't know the proper way to write it from this point.. Maybe regarding that Xn+1 and Xn which was Xn+1's parent? ----