Comprehensive Guide to Binary Trees, Traversals, and Binary Search Trees

Introduction to Trees and Non-Linear Data Structures

Classification of Data Structures:
- Linked Lists, Stacks, and Queues are classified as Linear Data Structures.
- Trees are classified as Non-Linear Data Structures.
Pointer and Node Connectivity:
- In a Linked List, each node contains a link that points strictly to one other node.
- In a Tree, each node may point to several other nodes, providing exceptional structural flexibility.
Application Example:
- A tree data structure can represent hierarchical relationships, such as a person and all of their descendants.
Node Architecture:
- Each tree node contains a data element (e.g., a name) alongside one or more pointers directed toward other tree nodes.

Fundamentals and Formal Definition of Binary Trees

Pointer Constraint:
- A binary tree node can possess at most $2$ pointers directed to other nodes.
Formal Definition:
- A Binary Tree is a finite set of elements that is either empty or partitioned into $3$ disjoint sub-sets:
  1. The first sub-set contains a single element known as the root of the tree.
  2. The other two sub-sets are themselves binary trees, termed the left sub-tree and the right sub-tree of the original tree.
Sub-tree Characteristics:
- A left sub-tree or a right sub-tree can be completely empty.
- Every individual element within a binary tree is termed a node.
Structural Examination of an Example Binary Tree:

Binary tree structure with six nodes A, B, C, D, E, F

*   The tree consists of  $6$  nodes in total, with node  $A$  serving as the root.
*   The left sub-tree is rooted at node  $B$ , and the right sub-tree is rooted at node  $C$ .
*   Two branches emanate directly from node  $A$ : branch to  $B$  on the left and branch to  $C$  on the right.
*   The absence of an emanating branch indicates an empty sub-tree (e.g., the right sub-tree of node  $B$  is empty).

Binary Tree Terminology and Hierarchical Relationships

Parent-Child (Father-Son) Terminology:
- Node $A$ is the father of node $B$ .
- Node $B$ is the left son of node $A$ .
- Node $C$ is the right son of node $A$ .
Leaf Nodes:
- A leaf node is defined as any node that has no sons.
- In the reference $6$ -node tree, the leaf nodes are: $D$ , $E$ , and $F$ .
Non-Leaf Nodes:
- A non-leaf node is any node that has one or more sons.
- In the reference $6$ -node tree, the non-leaf nodes are: $A$ , $B$ , and $C$ .
Ancestor Relationships:
- A node $n_1$ is said to be an ancestor of a node $n_2$ if $n_1$ is either the father of $n_2$ or the father of some ancestor of $n_2$ .
- Example: Node $A$ is an ancestor of node $B$ (and node $D$ ).
Brother (Sibling) Relationships:
- Two nodes are brothers if they are the left and right sons of the same father.
- Example: Nodes $B$ and $C$ are brothers; nodes $E$ and $F$ are brothers.

Non-Binary Trees and Non-Tree Structures

Structural Criteria for Non-Trees:

Examples of non-tree structures and cycles

*   Graphs containing cycles (closed circular paths) are non-trees.
*   Structures where a single node has multiple incoming parent links violate tree topology.
*   Structures where nodes have more than  $2$  children violate the strict definition of a binary tree.

Binary Tree Metrics and Specialized Classifications

Strictly Binary Tree:
- A binary tree is classified as a Strictly Binary Tree if every non-leaf node has a non-empty left sub-tree and a non-empty right sub-tree.
- Example node role partition:
  - Leaf nodes: $B$ , $F$ , $G$ , $E$
  - Non-leaf nodes: $A$ , $C$ , $D$
Degree of a Node:
- The degree of a node is defined as the total number of nodes connected directly to that particular node.
- The degree of a leaf node is always $1$ .
- Degree breakdown for example nodes:
  - $\text{Node } A = 2$
  - $\text{Node } B = 1$
  - $\text{Node } C = 3$
  - $\text{Node } D = 3$
  - $\text{Node } E = 1$
  - $\text{Node } F = 1$
  - $\text{Node } G = 1$
Level of a Node:
- The root node of a tree is established at level $0$ .
- Level assignments for example nodes:
  - Level $0$ : $A$
  - Level $1$ : $B$ , $C$
  - Level $2$ : $D$ , $E$
  - Level $3$ : $F$ , $G$
Depth of a Binary Tree:
- The depth of a binary tree is defined as the maximum level attained by any leaf within the tree.
- This metric is equivalent to the length of the longest path from the root node to any leaf node.
- In the reference example, the maximum depth is $3$ .
Complete Binary Tree:
- A complete binary tree of depth $d$ is a strictly binary tree in which all leaf nodes are situated at the exact same level $d$ .

*   A complete binary tree of depth  $2$  contains all leaves strictly positioned at level  $2$ .

Binary Tree Traversals

Concept of Traversal:
- Traversal of a binary tree entails visiting every single node in the tree exactly once.
- While linear lists have an inherent order from first to last, trees possess no single natural sequence for node visitation.
Memory Representation of a Node:
- A binary tree node is represented in storage with three distinct fields:
  - DATA: The substantive value or data element stored within the node.
  - LST LINK: Pointer to the Left Sub-Tree.
  - RST LINK: Pointer to the Right Sub-Tree.
Traversal Orders and Algorithmic Steps:
- Pre-order Traversal ( $N, L, R$ ):
  - Shorthand: (root node, left st, right st)
  - Step 1: Visit the Root.
  - Step 2: Traverse the left sub-tree in pre-order.
  - Step 3: Traverse the right sub-tree in pre-order.
- In-order Traversal ( $L, N, R$ ):
  - Shorthand: (Left st, root node, right st)
  - Step 1: Traverse the left sub-tree in pre-order.
  - Step 2: Visit the Root.
  - Step 3: Traverse the right sub-tree in pre-order.
- Post-order Traversal ( $L, R, N$ ):
  - Shorthand: (left st, right st, root node)
  - Step 1: Traverse the left sub-tree in pre-order.
  - Step 2: Traverse the right sub-tree in pre-order.
  - Step 3: Visit the Root.
Demonstration on Reference Binary Tree:

Five-node binary tree for traversal demonstration

*   Tree Layout: Root is node  $1$ ; left child is node  $2$ ; right child is node  $3$ . Node  $2$  has left child  $4$  and right child  $5$ .
*   **In-order Traversal** (Left, Root, Right):  $4, 2, 5, 1, 3$ 
*   **Pre-order Traversal** (Root, Left, Right):  $1, 2, 4, 5, 3$ 
*   **Post-order Traversal** (Left, Right, Root):  $4, 5, 2, 3, 1$

Binary Search Trees (BST)

Core Properties:
- A Binary Search Tree (BST) is a node-based binary tree data structure characterized by three fundamental properties:
  1. The left sub-tree of a node contains exclusively nodes with values less than the parent (root) node.
  2. The right sub-tree of a node contains exclusively nodes with values greater than the parent (root) node.
  3. Both the left and right sub-trees must each independently satisfy the requirements of a binary search tree.
Invariant Validation Example:

*   For the root node  $30$ :
    *   The left sub-tree contains values:  $15$ ,  $7$ ,  $22$ ,  $17$ ,  $27$ . None of these values are greater than or equal to  $30$ .
    *   The right sub-tree contains values:  $60$ ,  $45$ ,  $75$ . None of these values are less than  $30$ .
*   Sub-tree evaluations:
    *   At node  $15$ : Left child is  $7$  ( $7 < 15$ ); right child is  $22$  ( $22 > 15$ ).
    *   At node  $22$ : Left child is  $17$  ( $17 < 22$ ); right child is  $27$  ( $27 > 22$ ).
    *   At node  $60$ : Left child is  $45$  ( $45 < 60$ ); right child is  $75$  ( $75 > 60$ ).

Step-by-Step Construction of a Binary Search Tree

Insertion Dataset:
- Input sequence: $43, 10, 79, 90, 12, 54, 11, 9, 50$
BST Construction Algorithm:
1. Insert the first element ( $43$ ) as the root of the tree.
2. Read the next element: if it is lesser than the root node element, insert it into the left sub-tree.
3. Otherwise, insert it into the right sub-tree.
Detailed Step Progression:

Step-by-step BST construction from elements 43 to 50

*   **Step 1**: Insert  $43$ .
    *    $43$  is the first element and becomes the tree root.
*   **Step 2**: Insert  $10$ .
    *   Compare with root  $43$ :  $10 < 43$ .
    *    $10$  is attached as the left child of  $43$ .
*   **Step 3**: Insert  $79$ .
    *   Compare with root  $43$ :  $79 > 43$ .
    *    $79$  is attached as the right child of  $43$ .
*   **Step 4**: Insert  $90$ .
    *   Compare with root  $43$ :  $90 > 43$  (navigate right to  $79$ ).
    *   Compare with  $79$ :  $90 > 79$ .
    *    $90$  is attached as the right child of  $79$ .
*   **Step 5**: Insert  $12$ .
    *   Compare with root  $43$ :  $12 < 43$  (navigate left to  $10$ ).
    *   Compare with  $10$ :  $12 > 10$ .
    *    $12$  is attached as the right child of  $10$ .
*   **Step 6**: Insert  $54$ .
    *   Compare with root  $43$ :  $54 > 43$  (navigate right to  $79$ ).
    *   Compare with  $79$ :  $54 < 79$ .
    *    $54$  is attached as the left child of  $79$ .
*   **Step 7**: Insert  $11$ .
    *   Compare with root  $43$ :  $11 < 43$  (navigate left to  $10$ ).
    *   Compare with  $10$ :  $11 > 10$  (navigate right to  $12$ ).
    *   Compare with  $12$ :  $11 < 12$ .
    *    $11$  is attached as the left child of  $12$ .
*   **Step 8**: Insert  $9$ .
    *   Compare with root  $43$ :  $9 < 43$  (navigate left to  $10$ ).
    *   Compare with  $10$ :  $9 < 10$ .
    *    $9$  is attached as the left child of  $10$ .
*   **Step 9**: Insert  $50$ .
    *   Compare with root  $43$ :  $50 > 43$  (navigate right to  $79$ ).
    *   Compare with  $79$ :  $50 < 79$  (navigate left to  $54$ ).
    *   Compare with  $54$ :  $50 < 54$ .
    *    $50$  is attached as the left child of  $54$ .