Binary Tree

A binary tree is a special type of tree where each node can have at most two children usually called the left child and right child.

Binary trees are the foundation for many important data structures and algorithms from binary search trees and heaps to decision trees and expression trees.

Formally, a binary tree is:

• A finite set of nodes, either empty or consisting of:
• A root node.
• A left subtree (which is itself a binary tree).
• A right subtree (also a binary tree).

Each node has:

• At most two children.
• A left and/or right reference or pointer.
• Some stored value or data.

Binary Tree Terminology

Many terms you encounter with general trees also apply to binary trees, but here’s a binary-tree-specific refresher:

• Root: The top node with no parent.
• Leaf: A node with no children.
• Internal Node: A node with at least one child.
• Left Subtree / Right Subtree: The tree formed by the left or right child.
• Parent: The node directly above a given node.
• Sibling: Nodes with the same parent.
• Height: The longest path from the root to a leaf.
• Depth: The distance from the root to a particular node.
• Level: The layer number of a node, starting from 0 at the root.
• Balanced Tree: A tree where the heights of left and right subtrees differ by at most one.
• Complete Binary Tree: All levels are fully filled except possibly the last, which is filled left to right.
• Full (Proper) Binary Tree: Every node has either 0 or 2 children.
• Perfect Binary Tree: A full binary tree where all leaves are at the same level.
• Degenerate (Skewed) Tree: A tree where each parent has only one child, making it like a linked list.

Types of Binary Trees

1. Strictly Binary Tree

A binary tree where every node has either 0 or 2 children no node has only one child.

2. Full Binary Tree

This term is often used interchangeably with Strictly Binary Tree.

• Full Binary Tree: every node has either 0 or 2 children.
• Perfect Binary Tree: a full tree where all leaves are at the same depth.

3. Complete Binary Tree

A binary tree where all levels are fully filled except possibly the last, and the last level’s nodes are as far left as possible.

4. Strictly Complete Binary Tree

This is less common in formal textbooks, but some use it to refer to a tree that is both complete and strict/full.

Essentially, it’s a perfect binary tree where all levels are fully filled, and all leaves are at the same depth.

Binary Tree Operations

Common operations performed on binary trees include are:

1. Insertion

Adding a new node to the tree in an appropriate position.
In general binary trees, insertion doesn't follow a specific order like Binary Search Trees.

Approach: Usually inserted at the first available position (level-wise), typically using level-order traversal.

Example

   1
  / \
 2   3 

Insert 4 → Goes as the left child of 2

      1
    /   \
   2     3
  /
 4

2. Traversal

Definition: Visiting all nodes of the tree in a specific order.

a) Inorder Traversal (Left → Root → Right)

Gives sorted order for Binary Search Trees.

b) Preorder Traversal (Root → Left → Right)

Used to create a copy of the tree.

c) Postorder Traversal (Left → Right → Root)

Useful for deletion or post-processing.

d) Level-order Traversal

Traverse level by level using a queue.

3. Search

Find if a specific value exists in the tree. Use any traversal method (typically level-order or inorder).

4. Deletion

Remove a node from the tree and maintain its structure.

In Binary Tree, deletion often removes the deepest rightmost node or uses level-order logic.

In Binary Search Trees, 3 cases arise:

• Node is a leaf → Simply remove it.
• Node has one child → Replace it with its child.
• Node has two children → Replace with inorder successor or predecessor.

Example: Delete 50 from

     50                                     70
    /  \    -----> after delete ---->      /
  30    70                                30

Inorder successor is 70 → Replace 50 with 70.

5. Height / Depth Calculation

Height is the number of edges on the longest path from root to a leaf.

6. Count Nodes / Leaves

Total Nodes: Count all nodes recursively.

Leaf Nodes: Nodes with no children.

Internal Nodes: Nodes with at least one child.

7. Mirror / Invert the Tree

Swap left and right sub-trees of all nodes.

Example:

    1                           1
  /   \     --- Mirror -->    /   \
 2     3                     3     2

8. Check if Tree is Balanced

Height difference of left and right subtree of any node is not more than 1.

9. Find Maximum / Minimum

In Binary Tree: Traverse entire tree.

10. Diameter of a Tree

The length of the longest path between any two nodes in the tree. Can be computed recursively using height of left and right sub-trees.

Rules for Creating a General Binary Tree

When creating a general binary tree:

1. Each node can have 0, 1, or 2 children.
2. There is no strict ordering between parent and child node values.
3. Shape can vary depending on the insertion method:
   • Commonly, insertion follows level-order (from top to bottom, left to right).
4. The first node inserted becomes the root.
5. Next nodes fill the leftmost available spot at the lowest level.

This approach creates a complete binary tree-like structure, filling from left to right.

Example: Create a General Binary Tree Using Data

Given Data: 12, 18, 14, 15, 13, 7, 9, 11, 8, 3

We will build the tree using level-order insertion (top-down, left to right).

Step-by-step Construction

We insert the values in order

1. 12 → becomes the root.
2. 18 → goes to left of 12.
3. 14 → goes to right of 12.
4. 15 → goes to left of 18.
5. 13 → goes to right of 18.
6. 7 → goes to left of 14.
7. 9 → goes to right of 14.
8. 11 → goes to left of 15.
9. 8 → goes to right of 15.
10. 3 → goes to left of 13

Final Structure

              12
           /      \
         18        14
       /   \      /   \
     15    13    7     9
    /  \   /
  11   8  3

Each new node is placed in the next available left or right position level by level.

This creates a complete-like structure, but it’s not required to be perfect or sorted.

Binary Trees Representation

Binary trees are abstract data structures, but in practice, we need to represent them in memory so programs can work with them efficiently.

There are two main methods to represent a binary tree:

1. Arrays Representation of Binary Tree
2. Linked List Representation of Binary Tree

1. Array Representation (Sequential representation)

Uses an array or list to store the tree nodes by level order (breadth-first order).

Indexing rules (for 0-based index):

• Parent at index i.
• Left child at index 2i + 1.
• Right child at index 2i + 2.

    1
   / \
  2   3
 / \   \
4   5   6

The array would be:

• Index: 0 1 2 3 4 5
• Array: 1 2 3 4 5 6

Advantages

• Direct indexing; fast access by index.
• Very efficient for complete or perfect binary trees.

Disadvantages

• Wasteful for sparse trees (lots of unused slots).
• Difficult to resize dynamically.

C Program of Array (Sequential) Representation

#include <stdio.h>

#define MAX_SIZE 100

int main() {
    // Example tree:
    //     1
    //    / \
    //   2   3
    //  /
    // 4

    int tree[MAX_SIZE];
    for (int i = 0; i < MAX_SIZE; i++)
        tree[i] = -1; // Initialize empty slots

    tree[0] = 1;  // root
    tree[1] = 2;  // left child of root (2*0 + 1)
    tree[2] = 3;  // right child of root (2*0 + 2)
    tree[3] = 4;  // left child of node 2 (2*1 + 1)

    printf("Root: %d\n", tree[0]);
    printf("Left Child of Root: %d\n", tree[1]);
    printf("Right Child of Root: %d\n", tree[2]);
    printf("Left Child of Node 2: %d\n", tree[3]);

    return 0;
}

2. Linked Representation (Pointer-based)

Each node is represented as an object or struct containing the data (value stored in the node).

• A pointer/reference to the left child.
• A pointer/reference to the right child.

Structure Example

struct Node {
    int data;
    Node* left;
    Node* right;
};

How it works

• The root node is referenced by a separate pointer (often called root).
• Left and right pointers are used to navigate between nodes.
• You can easily build trees of any shape, including sparse or unbalanced trees.

Advantages

• Flexible; can represent any tree shape.
• Memory-efficient when the tree is sparse (few nodes).

Disadvantages

• Requires extra memory for storing pointers.
• Cannot directly index into arbitrary positions like in an array.

C Program of Linked (Pointer-based) Representation

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    // Example tree:
    //     1
    //    / \
    //   2   3

    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);

    printf("Root: %d\n", root->data);
    printf("Left Child: %d\n", root->left->data);
    printf("Right Child: %d\n", root->right->data);

    return 0;
}

Numerical Questions on General Binary Tree Creation

1. Create a general binary tree using the following level-order data: 25, 30, 15, 20, 10, 35, 40
   • Draw the tree.
   • Identify root, leaf, and internal nodes.
2. Given the data: 50, 20, 70, 10, 30, 60, 90, 5
   • Construct a general binary tree (not a BST) in level order.
   • Show the left and right child for each node.
3. Construct a general binary tree from the following data sequence: 8, 12, 6, 10, 5, 7
   • Draw the tree.
   • Write the preorder, inorder, and postorder traversals.
4. Insert the following values into a general binary tree using level-order strategy: 1, 2, 3, 4, 5, 6, 7, 8
   • Draw the resulting binary tree.
   • Count the number of:
   • Leaf nodes
   • Internal nodes
   • Total nodes
   • Height of the tree
5. Given numerical data: 100, 200, 300, 400, 500, 600
   • Build a general binary tree using level-order.
   • Represent the tree as an array (binary tree in array form).
6. Given the data values: 11, 22, 33, 44, 55, 66, 77, 88, 99
   • Construct the binary tree using level-order.
   • Perform inorder traversal and list the result.
7. Create a general binary tree from the data: 10, 5, 15, 2, 7, 12, 20, 1
   • Draw the tree.
   • What is the level of node 12?
   • What is the parent of node 1?