Binary Search Tree:

...

although the number of permutations of numbers is but those permutations output similar trees so the number of different trees is less than and equal to:

When inserting a new node into a binary search tree, we follow these steps:

1. Start at the root of the tree.
2. If the tree is empty, the new node becomes the root.
3. If the new node's value is less than the current node's value, move to the left child.
4. If the new node's value is greater than the current node's value, move to the right child.
5. Repeat steps 3 and 4 until a suitable empty position is found.
6. Insert the new node in that position.

this will work but for some cases this is bad because it is going to make our tree really deep e.g.
imagine if we want to add it from 1 to n one by one then we have a tree with height n-1 which slows down our search.

When deleting a node from a binary search tree, there are three cases to consider:

1. Deleting a node with no children (leaf node):
   In this case, we can simply remove the node from the tree.
2. Deleting a node with one child:
   In this case, we replace the node with its child.
3. Deleting a node with two children:
   This is the most complex case. We need to find the node with the next higher value (in-order successor) or the next lower value (in-order predecessor) and replace the node to be deleted with that node. Then we delete the in-order successor/predecessor node from its original position.

the proof was a pain in... so I did not include it here cause understanding it was already hard enough.😅

• if you want to find the biggest number always go right.

• if you want to find the smallest number always go left.

• if you want to find the successor (first number after it) of a number you have to follow 2 steps:

  1. If the node has a right child, the successor is the leftmost node in the right subtree. We move to the right child and then traverse as far left as possible until we reach a leaf node.

  2. If the node does not have a right child, we need to find the ancestor of the node for which the given node is in the left subtree. We move up the tree until we find an ancestor whose left child is the current node. The parent of this node is the successor.

• if you want to find the predecessor (first number after it) of a number you have to follow 2 steps:

  1. If the node has a left child, the predecessor is the rightmost node in the left subtree. We move to the left child and then traverse as far right as possible until we reach a leaf node.

  2. If the node does not have a left child, we need to find the ancestor of the node for which the given node is in the right subtree. We move up the tree until we find an ancestor whose right child is the current node. The parent of this node is the predecessor.

session 12