[AlgoMastery]
Topics›Tree›Complete Binary Tree
📖

Complete Binary Tree

Tree
~20 min read
5 practice problems

Complete Binary Tree

Overview

A complete binary tree is a binary tree in which all levels are completely filled except possibly the last level, and all nodes are as far left as possible. This structure provides optimal space utilization and is fundamental in heap implementations and efficient tree operations.

Key Properties

Definition

A complete binary tree satisfies two conditions:

  1. All levels except possibly the last are completely filled
  2. Nodes in the last level are filled from left to right

Complete vs Full vs Perfect Trees

  • Complete: All levels except possibly last are full, nodes filled left to right
  • Full: Every node has 0 or 2 children
  • Perfect: All internal nodes have 2 children and all leaves at same level

Implementation Examples

Node Structure

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Complete Tree Validation

function isCompleteTree(root) {
    if (root === null) return true;
    
    const queue = [root];
    let foundNull = false; // Flag to detect null nodes
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        if (node === null) {
            foundNull = true;
            continue;
        }
        
        // If we've seen a null node and now see a non-null node, it's not complete
        if (foundNull) return false;
        
        queue.push(node.left);
        queue.push(node.right);
    }
    
    return true;
}

Level-by-Level Construction

function buildCompleteTreeFromArray(arr) {
    if (arr.length === 0) return null;
    
    const root = new TreeNode(arr[0]);
    const queue = [root];
    let i = 1;
    
    while (queue.length > 0 && i < arr.length) {
        const node = queue.shift();
        
        // Add left child
        if (i < arr.length) {
            node.left = new TreeNode(arr[i]);
            queue.push(node.left);
            i++;
        }
        
        // Add right child
        if (i < arr.length) {
            node.right = new TreeNode(arr[i]);
            queue.push(node.right);
            i++;
        }
    }
    
    return root;
}

Complete Tree Characteristics

Height and Node Count

function getCompleteTreeHeight(root) {
    if (root === null) return -1;
    
    let height = 0;
    let currentLevel = [root];
    
    while (currentLevel.length > 0) {
        const nextLevel = [];
        
        for (const node of currentLevel) {
            if (node.left) nextLevel.push(node.left);
            if (node.right) nextLevel.push(node.right);
        }
        
        if (nextLevel.length > 0) {
            height++;
        }
        currentLevel = nextLevel;
    }
    
    return height;
}

Node Count in Complete Tree

function countNodesComplete(root) {
    if (root === null) return 0;
    
    // Calculate height to determine max possible nodes
    let leftHeight = 0;
    let current = root;
    while (current !== null) {
        leftHeight++;
        current = current.left;
    }
    
    // If last level is full, return 2^height - 1
    if (leftHeight === 0) return 0;
    
    // Otherwise, count nodes using level-by-level traversal
    const queue = [root];
    let count = 0;
    
    while (queue.length > 0) {
        const node = queue.shift();
        count++;
        
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    return count;
}

Complete Tree Operations

Insertion in Complete Tree

function insertCompleteTree(root, val) {
    if (root === null) return new TreeNode(val);
    
    // Find the parent for new node
    const queue = [root];
    let parent = null;
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        if (!node.left || !node.right) {
            parent = node;
            break;
        }
        
        queue.push(node.left);
        queue.push(node.right);
    }
    
    // Insert new node as left or right child
    if (!parent.left) {
        parent.left = new TreeNode(val);
    } else {
        parent.right = new TreeNode(val);
    }
    
    return root;
}

Deletion in Complete Tree

function deleteCompleteTree(root) {
    if (root === null) return null;
    
    // Find last node in tree
    const queue = [root];
    let lastNode = null;
    
    while (queue.length > 0) {
        const node = queue.shift();
        lastNode = node;
        
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    // Replace root value with last node's value
    const lastValue = lastNode.val;
    
    // Remove last node (find its parent)
    function removeLastNode(node, parent, isLeft) {
        if (node === null) return false;
        
        if (node === lastNode) {
            if (isLeft) parent.left = null;
            else parent.right = null;
            return true;
        }
        
        if (node.left === lastNode) {
            node.left = null;
            return true;
        }
        
        if (node.right === lastNode) {
            node.right = null;
            return true;
        }
        
        if (removeLastNode(node.left, node, true)) return true;
        return removeLastNode(node.right, node, false);
    }
    
    // Replace root with last node's value
    root.val = lastValue;
    
    return root;
}

Complete Tree vs Other Tree Types

Comparison Matrix

| Property | Complete Tree | Full Binary Tree | Perfect Tree |

|----------|---------------|---------------|------------|

| Level Filling | All levels except last full, last filled left-to-right | All internal nodes have 2 children | All nodes at same level |

| Space Efficiency | High | Moderate | High |

| Heap Implementation | Yes (Binary Heap) | No | Yes (Binary Heap) |

| Node Count | 2^h - 1 nodes at max | 2^n - 1 nodes | 2^n - 1 nodes |

| Height | h = log n | h = log n | h = log n |

Complete Tree Example

        1
       / \
      2   3
     / \ / \
    4  5 6 7

Incomplete Tree Example

        1
       / \
      2   3
     / \ / \
    4  5 6  7
       /
      8

Time and Space Complexity

| Operation | Time Complexity | Space Complexity |

|-----------|---------------|----------------|

| Validation | O(n) | O(w) |

| Insertion | O(log n) | O(1) |

| Deletion | O(log n) | O(1) |

| Count Nodes | O(n) | O(w) |

Where:

  • n = number of nodes in tree
  • w = maximum width of tree (queue space)

Common Variations

1. Binary Heap Implementation

class BinaryHeap {
    constructor() {
        this.heap = [];
    }
    
    insert(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }
    
    bubbleUp(index) {
        if (index === 0) return;
        
        const parentIndex = Math.floor((index - 1) / 2);
        if (this.heap[parentIndex] >= this.heap[index]) return;
        
        [this.heap[parentIndex], this.heap[index]] = 
            [this.heap[index], this.heap[parentIndex]];
        this.bubbleUp(parentIndex);
    }
    
    extractMax() {
        if (this.heap.length === 0) return null;
        
        const max = this.heap[0];
        const last = this.heap.pop();
        
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
        
        return max;
    }
    
    bubbleDown(index) {
        const leftChild = 2 * index + 1;
        const rightChild = 2 * index + 2;
        
        let maxIndex = index;
        
        if (leftChild < this.heap.length && 
            this.heap[leftChild] > this.heap[maxIndex]) {
            maxIndex = leftChild;
        }
        
        if (rightChild < this.heap.length && 
            this.heap[rightChild] > this.heap[maxIndex]) {
            maxIndex = rightChild;
        }
        
        if (maxIndex !== index) {
            [this.heap[index], this.heap[maxIndex]] = 
                [this.heap[maxIndex], this.heap[index]];
            this.bubbleDown(maxIndex);
        }
    }
}

2. Complete Tree with Level Tracking

function getCompleteTreeLevels(root) {
    if (root === null) return [];
    
    const levels = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        levels.push(currentLevel);
    }
    
    return levels;
}

Common Mistakes to Avoid

1. Incorrect Level Filling Logic

// ❌ Wrong - Not maintaining left-to-right filling order
function wrongCompleteTreeInsert(root, val) {
    if (root === null) return new TreeNode(val);
    
    // This doesn't properly maintain the complete tree property
    const queue = [root];
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        if (!node.left) {
            node.left = new TreeNode(val);
            return root;
        }
        
        if (!node.right) {
            node.right = new TreeNode(val);
            return root;
        }
        
        queue.push(node.left);
        queue.push(node.right);
    }
}

2. Missing Null Checks

// ❌ Wrong - Not handling edge cases properly
function incompleteCompleteCheck(node) {
    // Missing proper null checking and validation logic
    const queue = [node];
    
    while (queue.length > 0) {
        const current = queue.shift();
        
        // Missing proper validation of complete tree properties
        if (current.left) queue.push(current.left);
        if (current.right) queue.push(current.right);
    }
    
    return true; // Always returns true
}

3. Incorrect Height Calculation

// ❌ Wrong - Not properly calculating tree height for complete trees
function wrongHeight(root) {
    if (root === null) return 0;
    
    // This doesn't account for complete tree structure properly
    let height = 0;
    let current = root;
    
    while (current.left) {
        height++;
        current = current.left;
    }
    
    return height;
}

Comparison with Other Tree Types

Complete vs Perfect Binary Tree

// Perfect tree has all levels completely filled
function isPerfectTree(root) {
    if (root === null) return true;
    
    const height = getTreeHeight(root);
    return isPerfectAtHeight(root, 0, height);
}

function isPerfectAtHeight(node, currentLevel, targetHeight) {
    if (node === null) return currentLevel === targetHeight;
    
    if (currentLevel === targetHeight) {
        return node.left === null && node.right === null;
    }
    
    return isPerfectAtHeight(node.left, currentLevel + 1, targetHeight) &&
           isPerfectAtHeight(node.right, currentLevel + 1, targetHeight);
}

Complete vs Full Binary Tree

// Full tree has 0 or 2 children for every node
function isFullTree(root) {
    if (root === null) return true;
    
    // Leaf node
    if (root.left === null && root.right === null) return true;
    
    // Both children exist or none
    if (root.left !== null && root.right !== null) {
        return isFullTree(root.left) && isFullTree(root.right);
    }
    
    // Only one child exists - not full tree
    return false;
}

Real-World Applications

1. Heap-Based Algorithms

// Priority queue implementation using complete binary tree
class PriorityQueue {
    constructor() {
        this.heap = [];
    }
    
    enqueue(item, priority) {
        // Insert at end of complete tree structure
        this.heap.push({item, priority});
        this.bubbleUp(this.heap.length - 1);
    }
    
    dequeue() {
        // Remove root and restructure
        if (this.heap.length === 0) return null;
        
        const min = this.heap[0];
        const last = this.heap.pop();
        
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
        
        return min.item;
    }
    
    bubbleUp(index) {
        // Bubble up to maintain heap property
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            
            if (this.heap[parentIndex].priority <= this.heap[index].priority) break;
            
            [this.heap[parentIndex], this.heap[index]] = 
                [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }
    
    bubbleDown(index) {
        // Bubble down to maintain heap property
        const length = this.heap.length;
        
        while (true) {
            let leftChild = 2 * index + 1;
            let rightChild = 2 * index + 2;
            let smallest = index;
            
            if (leftChild < length && 
                this.heap[leftChild].priority < this.heap[smallest].priority) {
                smallest = leftChild;
            }
            
            if (rightChild < length && 
                this.heap[rightChild].priority < this.heap[smallest].priority) {
                smallest = rightChild;
            }
            
            if (smallest === index) break;
            
            [this.heap[index], this.heap[smallest]] = 
                [this.heap[smallest], this.heap[index]];
            index = smallest;
        }
    }
}

2. File System Organization

// Hierarchical file system using complete tree structure for efficient navigation
class FileSystemTree {
    constructor() {
        this.root = null;
    }
    
    // Maintain complete structure for efficient traversal
    addDirectory(path) {
        // Insert in appropriate position to maintain completeness
        this.root = this.insertComplete(this.root, path);
    }
    
    isComplete() {
        return isCompleteTree(this.root);
    }
}

3. Memory Management

// Memory allocation using complete binary tree structure
class MemoryManager {
    constructor() {
        this.freeBlocks = new BinaryHeap(); // Complete tree structure
    }
    
    allocate(size) {
        // Find best fit in complete heap structure
        return this.freeBlocks.extractMin();
    }
    
    deallocate(block) {
        // Insert back into complete tree structure
        this.freeBlocks.insert(block);
    }
}

Performance Optimization Tips

1. Efficient Insertion

function optimizedCompleteInsert(root, val) {
    // Use array-based approach for O(1) insertion
    const queue = [root];
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        if (!node.left) {
            node.left = new TreeNode(val);
            return root;
        }
        
        if (!node.right) {
            node.right = new TreeNode(val);
            return root;
        }
        
        queue.push(node.left);
        queue.push(node.right);
    }
    
    return root;
}

2. Space-Efficient Validation

function spaceEfficientCompleteCheck(root) {
    if (root === null) return true;
    
    const queue = [root];
    let foundNull = false;
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        if (node === null) {
            foundNull = true;
            continue;
        }
        
        if (foundNull && node !== null) return false;
        
        queue.push(node.left);
        queue.push(node.right);
    }
    
    return true;
}

3. Batch Operations

function batchInsertComplete(root, values) {
    // Insert multiple values efficiently maintaining completeness
    if (root === null) return null;
    
    const queue = [root];
    let i = 0;
    
    while (queue.length > 0 && i < values.length) {
        const node = queue.shift();
        
        // Insert left child if needed
        if (i < values.length && !node.left) {
            node.left = new TreeNode(values[i++]);
            queue.push(node.left);
        }
        
        // Insert right child if needed
        if (i < values.length && !node.right) {
            node.right = new TreeNode(values[i++]);
            queue.push(node.right);
        }
        
        // Add existing children to queue for processing
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    return root;
}

Common Interview Questions

1. Validate Complete Binary Tree

function isCompleteBinaryTree(root) {
    if (root === null) return true;
    
    const queue = [root];
    let foundNull = false;
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        if (node === null) {
            foundNull = true;
            continue;
        }
        
        if (foundNull && node !== null) return false;
        
        queue.push(node.left);
        queue.push(node.right);
    }
    
    return true;
}

2. Count Nodes in Complete Tree

function countNodesComplete(root) {
    if (root === null) return 0;
    
    let leftHeight = 0;
    let rightHeight = 0;
    let current = root;
    
    // Calculate left height
    while (current !== null) {
        leftHeight++;
        current = current.left;
    }
    
    current = root;
    
    // Calculate right height
    while (current !== null) {
        rightHeight++;
        current = current.right;
    }
    
    // If heights are equal, it's a perfect tree
    if (leftHeight === rightHeight) {
        return Math.pow(2, leftHeight) - 1;
    }
    
    // Otherwise, recursively count nodes
    return 1 + countNodesComplete(root.left) + countNodesComplete(root.right);
}

3. Find Last Node in Complete Tree

function findLastNode(root) {
    if (root === null) return null;
    
    const queue = [root];
    let lastNode = root;
    
    while (queue.length > 0) {
        const node = queue.shift();
        lastNode = node;
        
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    return lastNode;
}

Best Practices

1. Consistent Tree Structure

Always maintain the complete tree property during insertions and deletions.

2. Efficient Memory Usage

Use array-based representations for better cache locality and memory efficiency.

3. Proper Validation

Always validate that the tree maintains complete structure after operations.

4. Optimized Algorithms

Implement algorithms that take advantage of the complete tree properties for better performance.

Key Takeaways

  1. Complete Tree Properties: All levels filled except last, nodes filled left-to-right
  2. Heap Implementation: Complete trees form the basis of binary heaps and priority queues
  3. Space Efficiency: Optimal space utilization for tree structures
  4. Performance: O(log n) operations for insertion, deletion, and search
  5. Real-World Applications: Database indexing, file systems, memory management, and algorithm design

Complete binary trees are fundamental data structures that provide optimal performance characteristics for many algorithms and systems where space efficiency and predictable operation times are crucial.

← PreviousBalanced Binary TreeNext →Full Binary Tree