Binary Tree: Core Concepts and Operations Explained

Binary Tree

A Binary Tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child. Unlike arrays or linked lists (linear structures), binary trees organize data in a parent-child hierarchy, enabling efficient traversal, search, insertion, and deletion operations. They serve as the foundation for more advanced structures like Binary Search Trees (BSTs), AVL Trees, Red-Black Trees, and Heaps, with applications in databases, compilers, and pathfinding algorithms.

I. Core Concepts & Terminology

1. Basic Definitions

Node: The fundamental unit of a binary tree, containing a value (data) and references/pointers to left and right children.
Root: The topmost node of the tree (no parent).
Leaf Node: A node with no children (left and right pointers are None).
Internal Node: A node with at least one child.
Parent/Child: A node directly above another node is its parent; the node below is its child.
Sibling: Nodes sharing the same parent.
Ancestor/Descendant: A node reachable by moving up the tree from a given node (ancestor) or down (descendant).

2. Key Properties

Height: The number of edges from a node to the deepest leaf (height of root = tree height; height of leaf = 0).
Depth: The number of edges from the root to a given node (depth of root = 0).
Size: The total number of nodes in the tree.
Degree: The number of children a node has (max degree = 2 for binary trees).

3. Common Binary Tree Types

Type	Description
Full Binary Tree	Every node has 0 or 2 children (no nodes with 1 child).
Complete Binary Tree	All levels except the last are fully filled; last level nodes are left-aligned.
Perfect Binary Tree	All levels are fully filled (all leaves have the same depth; size = \(2^h – 1\), where h = height).
Skewed Binary Tree	All nodes have only one child (left-skewed: all left children; right-skewed: all right children).
Binary Search Tree (BST)	Left subtree of a node contains values < node’s value; right subtree contains values > node’s value (enables efficient search).

II. Binary Tree Implementation (Python)

We’ll implement a binary tree using a TreeNode class, with methods for traversal, insertion, deletion, and property calculations.

1. TreeNode Class

python

运行

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # Node value
        self.left = left     # Left child pointer
        self.right = right   # Right child pointer

    def __str__(self):
        return str(self.val)  # String representation of node value

2. Binary Tree Class (with Core Operations)

python

运行

class BinaryTree:
    def __init__(self, root=None):
        self.root = root  # Root node of the tree

    # -------------------------- Traversal Methods --------------------------
    # 1. Depth-First Search (DFS) Traversals
    def pre_order(self, node, traversal=None):
        """Pre-order: Visit → Left → Right (recursive)"""
        if traversal is None:
            traversal = []
        if node:
            traversal.append(node.val)
            self.pre_order(node.left, traversal)
            self.pre_order(node.right, traversal)
        return traversal

    def in_order(self, node, traversal=None):
        """In-order: Left → Visit → Right (recursive; yields sorted order for BST)"""
        if traversal is None:
            traversal = []
        if node:
            self.in_order(node.left, traversal)
            traversal.append(node.val)
            self.in_order(node.right, traversal)
        return traversal

    def post_order(self, node, traversal=None):
        """Post-order: Left → Right → Visit (recursive)"""
        if traversal is None:
            traversal = []
        if node:
            self.post_order(node.left, traversal)
            self.post_order(node.right, traversal)
            traversal.append(node.val)
        return traversal

    # 2. Breadth-First Search (BFS) Traversal (Level-order)
    def level_order(self):
        """Level-order: Traverse node by level (top to bottom, left to right; iterative)"""
        if not self.root:
            return []
        traversal = []
        queue = [self.root]  # Use queue to track nodes at current level
        while queue:
            current = queue.pop(0)  # Dequeue front node
            traversal.append(current.val)
            # Enqueue left child first (for left-to-right order)
            if current.left:
                queue.append(current.left)
            if current.right:
                queue.append(current.right)
        return traversal

    # -------------------------- Property Calculations --------------------------
    def height(self, node):
        """Calculate height of a node (recursive)"""
        if not node:
            return -1  # Height of empty tree = -1 (edges); use 0 for nodes
        left_height = self.height(node.left)
        right_height = self.height(node.right)
        return 1 + max(left_height, right_height)

    def size(self, node):
        """Calculate size of the tree (number of nodes; recursive)"""
        if not node:
            return 0
        return 1 + self.size(node.left) + self.size(node.right)

    def is_full(self, node):
        """Check if tree is full (every node has 0 or 2 children; recursive)"""
        if not node:
            return True  # Empty tree is full
        # Node has one child → not full
        if (node.left is None and node.right is not None) or (node.left is not None and node.right is None):
            return False
        # Recursively check left and right subtrees
        return self.is_full(node.left) and self.is_full(node.right)

    def is_complete(self):
        """Check if tree is complete (iterative; uses BFS to track empty nodes)"""
        if not self.root:
            return True
        queue = [self.root]
        found_empty = False  # Flag to detect first empty node
        while queue:
            current = queue.pop(0)
            if not current:
                found_empty = True
            else:
                if found_empty:
                    return False  # Non-empty node after empty node → not complete
                queue.append(current.left)
                queue.append(current.right)
        return True

    # -------------------------- Insertion & Deletion --------------------------
    def insert_level_order(self, val):
        """Insert node at the first available position (level-order; maintains completeness)"""
        new_node = TreeNode(val)
        if not self.root:
            self.root = new_node
            return
        queue = [self.root]
        while queue:
            current = queue.pop(0)
            # Insert left child if empty
            if not current.left:
                current.left = new_node
                return
            # Insert right child if empty
            if not current.right:
                current.right = new_node
                return
            # Enqueue children if both are present
            queue.append(current.left)
            queue.append(current.right)

    def delete_deepest(self, node):
        """Helper: Delete the deepest rightmost node (used for deletion)"""
        queue = [node]
        parent = None
        deepest_node = None
        # Find deepest node and its parent
        while queue:
            parent = deepest_node
            deepest_node = queue.pop(0)
            if deepest_node.left:
                queue.append(deepest_node.left)
            if deepest_node.right:
                queue.append(deepest_node.right)
        # Delete deepest node (update parent's pointer)
        if parent:
            if parent.right == deepest_node:
                parent.right = None
            else:
                parent.left = None
        else:
            self.root = None  # Tree had only one node
        return deepest_node.val  # Return value of deleted node

    def delete(self, val):
        """Delete a node with given value (replace with deepest node; iterative)"""
        if not self.root:
            return False  # Tree is empty
        queue = [self.root]
        target_node = None
        parent = None
        # Find target node and its parent
        while queue:
            parent = queue[0]
            current = queue.pop(0)
            if current.val == val:
                target_node = current
            if current.left:
                queue.append(current.left)
            if current.right:
                queue.append(current.right)
        if not target_node:
            return False  # Value not found
        # Replace target node's value with deepest node's value
        deepest_val = self.delete_deepest(self.root)
        target_node.val = deepest_val
        return True

3. Test the Binary Tree

python

运行

if __name__ == "__main__":
    # Build a sample binary tree:
    #        1
    #       / \
    #      2   3
    #     / \
    #    4   5
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    bt = BinaryTree(root)

    # Traversals
    print("Pre-order Traversal:", bt.pre_order(bt.root))    # Output: [1, 2, 4, 5, 3]
    print("In-order Traversal:", bt.in_order(bt.root))      # Output: [4, 2, 5, 1, 3]
    print("Post-order Traversal:", bt.post_order(bt.root))  # Output: [4, 5, 2, 3, 1]
    print("Level-order Traversal:", bt.level_order())       # Output: [1, 2, 3, 4, 5]

    # Properties
    print("\nTree Height:", bt.height(bt.root))             # Output: 2 (edges: 1→2→4)
    print("Tree Size:", bt.size(bt.root))                   # Output: 5
    print("Is Full Tree?", bt.is_full(bt.root))             # Output: True (all nodes have 0 or 2 children)
    print("Is Complete Tree?", bt.is_complete())            # Output: True

    # Insertion
    bt.insert_level_order(6)  # Insert 6 as right child of 3
    print("\nLevel-order after inserting 6:", bt.level_order())  # Output: [1, 2, 3, 4, 5, 6]

    # Deletion
    bt.delete(2)  # Delete node with value 2 (replace with deepest node 6)
    print("Level-order after deleting 2:", bt.level_order())    # Output: [1, 6, 3, 4, 5]

III. Key Operations Explained

1. Traversal

Traversal is the process of visiting every node in the tree exactly once. Binary trees support two main traversal categories:

Depth-First Search (DFS)

Pre-order: Visit the current node first, then recursively traverse the left and right subtrees. Used for creating tree copies or prefix expressions.
In-order: Traverse the left subtree first, then visit the current node, then the right subtree. For BSTs, this yields nodes in sorted order.
Post-order: Traverse left and right subtrees first, then visit the current node. Used for deleting the tree or postfix expressions.

Breadth-First Search (BFS)

Level-order: Traverse nodes level by level (top to bottom, left to right). Uses a queue to track nodes at the current level. Ideal for finding the shortest path in unweighted trees or inserting nodes while maintaining completeness.

2. Insertion

Level-order Insertion: Inserts nodes at the first available position (leftmost empty slot), ensuring the tree remains complete. This is the most common insertion method for general binary trees.

3. Deletion

Deletion in binary trees is non-trivial (since we can’t leave gaps in the hierarchy). The standard approach is:

Find the target node to delete.
Find the deepest rightmost node (last node in level-order traversal).
Replace the target node’s value with the deepest node’s value.
Delete the deepest node.

This method preserves the tree’s structure and avoids breaking parent-child relationships.

4. Property Calculations

Height: Recursively compute the height of left and right subtrees, then take the maximum and add 1 (for the current node).
Size: Sum 1 (current node) with the size of left and right subtrees.
Full Tree Check: Ensure no node has exactly one child.
Complete Tree Check: Use BFS to detect if any non-empty node comes after an empty node (invalid for complete trees).

IV. Time & Space Complexity

Operation	Time Complexity	Space Complexity	Explanation
Traversal (DFS)	O(n)	O(h)	– n = number of nodes (visits all nodes).- h = tree height (call stack space; \(h = \log n\) for balanced trees, \(h = n\) for skewed trees).
Traversal (BFS)	O(n)	O(w)	– w = maximum width of the tree (queue space; \(w = n/2\) for perfect trees).
Insertion (Level-order)	O(n)	O(w)	May require traversing all nodes to find the first empty slot.
Deletion	O(n)	O(w)	Requires finding the target node and the deepest node (both O(n) in worst case).
Property Calculations (Height/Size/Full/Complete)	O(n)	O(h) (recursive) / O(w) (iterative)	Traverses the tree once to compute properties.

V. Practical Applications of Binary Trees

Binary Search Trees (BSTs): Enable efficient search, insertion, and deletion (O(log n) for balanced trees) — used in databases and sorted data storage.
Heaps: Complete binary trees used for priority queues (e.g., Dijkstra’s Algorithm, Huffman Coding).
Syntax Trees: Used in compilers to represent the structure of expressions (e.g., arithmetic, logical) during parsing.
Pathfinding Algorithms: Used in maze solving, game AI (e.g., minimax algorithm for chess), and decision trees.
Database Indexing: Balanced binary trees (AVL, Red-Black) are used to index database tables for fast querying.
Huffman Coding: A compression algorithm that uses a binary tree to assign variable-length codes to characters based on frequency.

VI. Binary Tree vs. Other Data Structures

Data Structure	Binary Tree	Array	Linked List
Structure	Hierarchical	Linear (contiguous)	Linear (non-contiguous)
Search Time	O(n) (unsorted) / O(log n) (BST)	O(n) (linear) / O(log n) (sorted)	O(n) (linear)
Insertion/Deletion	O(n) (general) / O(log n) (BST)	O(n) (shift elements)	O(1) (at head/tail)
Space Efficiency	O(n) (nodes + pointers)	O(n) (contiguous)	O(n) (nodes + pointers)
Use Case	Hierarchical data, sorting, indexing	Fast random access	Dynamic size, frequent insertions/deletions