Data Structures - Binary Search Trees

If each node has 0 child, 1 child or 2 children. Empty trees is also a valid binary tree.

Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.

Deleting a node with one child: Remove the node and replace it with its child.

Deleting a node with two children

• left child node = parent's left node
• right child node = parent's right node

• Check if the left child's node is NULL && right child's node is NULL
• then set parent's left node = null

• left child node = parent's left node
• right child node = parent's right node

• if the left child's left node is null then
• set the parent's left node to it's left child's right node

• if the left child's right node is null then
• set the parent's left node to it's left child's left node

• left child node = parent's left node
• right child node = parent's right node

set the parent's left node to it's left child's right node

and 

leftChildNode.getRightNode().setLeftNode(leftChildNode.getLeftNode());

The length of the path from the root to the node.

The length of the path from that node to the deepest node.

The number of descendants it has including itself.

Every node in a tree has only one child.

If each node has exactly 2 children or no children.

If each node has exactly 2 children and all leaf nodes are at same level.

If all leaf nodes are at height h or h-1 and also without any missing number in the sequence.

Value-Left-Right

Left-Right-Value