[AlgoMastery]
Topics›Tree›Full Binary Tree
📖

Full Binary Tree

Tree
~20 min read
5 practice problems

Full Binary Tree

Overview

A full binary tree (also called a proper or strict binary tree) is a binary tree in which every node has either 0 or 2 children. In other words, all nodes have either no children (leaf nodes) or exactly two children. This structure is fundamental in many tree algorithms and data structures.

Key Properties

Definition

A full binary tree satisfies the condition that every node has either:

  • 0 children (leaf nodes)
  • 2 children (internal nodes with both left and right subtrees)

Characteristics

  1. Every internal node has exactly 2 children
  2. All leaf nodes are at the same level (in complete trees)
  3. Maximum number of nodes at height h: 2^h nodes
  4. Minimum number of nodes for height h: h + 1 nodes

Implementation Examples

Node Structure

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

Full Tree Validation

function isFullBinaryTree(root) {
    // Empty tree is considered full
    if (root === null) return true;
    
    // Leaf node - satisfies full tree property
    if (root.left === null && root.right === null) {
        return true;
    }
    
    // Internal node must have both children
    if (root.left !== null && root.right !== null) {
        return isFullBinaryTree(root.left) && isFullBinaryTree(root.right);
    }
    
    // Node has only one child - not full tree
    return false;
}

Count Nodes in Full Tree

function countNodesFullTree(root) {
    if (root === null) return 0;
    
    // Leaf node
    if (root.left === null && root.right === null) {
        return 1;
    }
    
    // Internal node with two children
    return 1 + countNodesFullTree(root.left) + countNodesFullTree(root.right);
}

Create Full Binary Tree from Array

function buildFullBinaryTree(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();
        
        // Create left child if available
        if (i < arr.length) {
            node.left = new TreeNode(arr[i]);
            queue.push(node.left);
            i++;
        }
        
        // Create right child if available
        if (i < arr.length) {
            node.right = new TreeNode(arr[i]);
            queue.push(node.right);
            i++;
        }
    }
    
    return root;
}

Full Tree Characteristics

Height and Node Relationships

function getFullTreeHeight(root) {
    if (root === null) return -1;
    
    const leftHeight = getFullTreeHeight(root.left);
    const rightHeight = getFullTreeHeight(root.right);
    
    return 1 + Math.max(leftHeight, rightHeight);
}

function maxNodesInFullTree(height) {
    // For a full binary tree of height h, maximum nodes = 2^(h+1) - 1
    return Math.pow(2, height + 1) - 1;
}

function minNodesInFullTree(height) {
    // For a full binary tree of height h, minimum nodes = 2^h + 1
    return Math.pow(2, height) + 1;
}

Node Count Analysis

function countNodesFullTreeOptimized(root) {
    // If tree is empty, return 0
    if (root === null) return 0;
    
    // If it's a leaf node, return 1
    if (root.left === null && root.right === null) return 1;
    
    // For full tree, we can calculate more efficiently
    const leftCount = countNodesFullTree(root.left);
    const rightCount = countNodesFullTree(root.right);
    
    return 1 + leftCount + rightCount;
}

Full Tree Operations

Insertion in Full Tree

function insertFullTree(root, val) {
    // For a full tree, insertion creates new leaf nodes
    if (root === null) return new TreeNode(val);
    
    // Find appropriate position to maintain full tree property
    const queue = [root];
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        // If node has no children, insert here
        if (node.left === null && node.right === null) {
            node.left = new TreeNode(val);
            return root;
        }
        
        // If only left child exists, insert right
        if (node.left !== null && node.right === null) {
            node.right = new TreeNode(val);
            return root;
        }
        
        // If both children exist, continue searching
        if (node.left !== null) queue.push(node.left);
        if (node.right !== null) queue.push(node.right);
    }
    
    return root;
}

Deletion in Full Tree

function deleteFullTree(root, val) {
    if (root === null) return null;
    
    // If root is to be deleted
    if (root.val === val) {
        // For full tree, deletion requires restructuring
        return null; // Simple case - remove entire tree if root is deleted
    }
    
    const queue = [root];
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        if (node.left !== null && node.left.val === val) {
            // Remove left child
            node.left = null;
            return root;
        }
        
        if (node.right !== null && node.right.val === val) {
            // Remove right child
            node.right = null;
            return root;
        }
        
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    return root;
}

Full Tree vs Other Tree Types

Comparison Matrix

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

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

| Node Children | 0 or 2 children | 0, 1, or 2 children | 0 or 2 children |

| Internal Nodes | All have 2 children | May have 0, 1, or 2 children | All internal nodes have 2 children |

| Leaf Distribution | Not necessarily at same level | Leaves fill left-to-right | All leaves at same level |

| Height | h = log n (approx) | h = log n (approx) | h = log n |

| Node Count | n = 2^h - 1 (perfect) | n ≤ 2^h+1 - 1 | n = 2^h+1 - 1 |

Full Tree Example

        A
       / \
      B   C
     / \ / \
    D E F G

Non-Full Tree Example

        A
       / \
      B   C
     / 
    D

Time and Space Complexity

| Operation | Time Complexity | Space Complexity |

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

| Validation | O(n) | O(h) |

| Count Nodes | O(n) | O(h) |

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

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

Where:

  • n = number of nodes in tree
  • h = height of tree (recursion stack space)

Common Variations

1. Perfect Binary Tree (Special Case of Full)

function isPerfectBinaryTree(root) {
    if (root === null) return true;
    
    // Check if tree is full and all leaves at same level
    const height = getTreeHeight(root);
    return isPerfectAtHeight(root, 0, height);
}

function isPerfectAtHeight(node, currentLevel, targetHeight) {
    if (node === null) return currentLevel === targetHeight;
    
    // If leaf node, must be at target level
    if (node.left === null && node.right === null) {
        return currentLevel === targetHeight;
    }
    
    // Must have both children for perfect tree
    if (node.left === null || node.right === null) {
        return false;
    }
    
    return isPerfectAtHeight(node.left, currentLevel + 1, targetHeight) &&
           isPerfectAtHeight(node.right, currentLevel + 1, targetHeight);
}

2. Full Tree with Level Tracking

function getFullTreeLevels(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;
}

3. Full Tree with Node Properties

class FullTreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.level = 0;
        this.isLeaf = false;
    }
    
    static createFullTreeFromArray(arr) {
        if (arr.length === 0) return null;
        
        const root = new FullTreeNode(arr[0]);
        const queue = [root];
        let i = 1;
        
        while (queue.length > 0 && i < arr.length) {
            const node = queue.shift();
            
            if (i < arr.length) {
                node.left = new FullTreeNode(arr[i++]);
                queue.push(node.left);
            }
            
            if (i < arr.length) {
                node.right = new FullTreeNode(arr[i++]);
                queue.push(node.right);
            }
        }
        
        return root;
    }
}

Common Mistakes to Avoid

1. Incorrect Full Tree Definition

// ❌ Wrong - Confusing with complete tree properties
function wrongFullTreeCheck(node) {
    // This doesn't properly check for full binary tree property
    if (node === null) return true;
    
    // Only checking if node has children, not proper structure
    if (node.left === null && node.right === null) return true;
    
    // Missing proper validation logic
    return false; // Always returns false in some cases
}

2. Missing Node Type Validation

// ❌ Wrong - Not properly handling different node types
function incompleteFullTreeCheck(node) {
    if (node === null) return true;
    
    // This logic is incomplete and incorrect
    if (node.left === null) {
        return node.right === null; // Only checks for leaf nodes
    }
    
    if (node.right === null) {
        return node.left === null; // Only checks for leaf nodes
    }
    
    // Missing recursive validation
    return true; // Always returns true incorrectly
}

3. Incorrect Height Calculation

// ❌ Wrong - Not properly calculating tree height for full trees
function wrongHeightCalculation(root) {
    if (root === null) return 0;
    
    // This doesn't properly account for full tree structure
    let height = 0;
    let current = root;
    
    while (current !== null) {
        // This assumes left subtree is always deeper
        current = current.left;
        height++;
    }
    
    return height; // Incorrect calculation
}

Comparison with Other Tree Types

Full vs Complete Binary Tree

// Complete tree allows nodes with 0 or 1 or 2 children
function isCompleteTree(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;
}

// Full tree requires 0 or 2 children for every node
function isFullTree(root) {
    if (root === null) return true;
    
    if (root.left === null && root.right === null) {
        return true;
    }
    
    if (root.left !== null && root.right !== null) {
        return isFullTree(root.left) && isFullTree(root.right);
    }
    
    return false;
}

Full vs Perfect Binary Tree

// Perfect tree is both full and complete with all leaves at same level
function isPerfectTree(root) {
    if (root === null) return true;
    
    // Check if tree is full
    const isFull = isFullBinaryTree(root);
    
    // Check if all leaves are at same level
    const height = getTreeHeight(root);
    const isCompleteAtLevel = isCompleteAtLevel(root, 0, height);
    
    return isFull && isCompleteAtLevel;
}

function getTreeHeight(root) {
    if (root === null) return -1;
    
    const leftHeight = getTreeHeight(root.left);
    const rightHeight = getTreeHeight(root.right);
    
    return 1 + Math.max(leftHeight, rightHeight);
}

Real-World Applications

1. Expression Tree Parsing

// Expression trees in compilers use full binary tree structure
class ExpressionTree {
    constructor() {
        this.root = null;
    }
    
    // Build full tree for mathematical expressions
    buildExpressionTree(expression) {
        // Each operator node has exactly 2 operands (children)
        return this.parseExpression(expression);
    }
    
    isFullExpressionTree() {
        return isFullBinaryTree(this.root);
    }
}

2. Huffman Coding Trees

// Huffman trees are typically full binary trees
class HuffmanTree {
    constructor() {
        this.root = null;
    }
    
    buildHuffmanTree(frequencies) {
        // Create full binary tree for optimal encoding
        return this.buildFullTree(frequencies);
    }
    
    isHuffmanValid() {
        // Validate that tree is full (properly structured)
        return isFullBinaryTree(this.root);
    }
}

3. File System Directory Structures

// File system directory trees (when properly structured)
class FileSystemTree {
    constructor() {
        this.root = null;
    }
    
    // Maintain full tree structure for efficient traversal
    addDirectory(path) {
        // Ensure directory structure maintains full tree properties where possible
        this.root = this.insertFullTree(this.root, path);
    }
    
    isFullStructure() {
        return isFullBinaryTree(this.root);
    }
}

Performance Optimization Tips

1. Efficient Node Counting

function optimizedFullTreeCount(root) {
    // For full trees, we can use mathematical properties when possible
    if (root === null) return 0;
    
    // If we know it's a full tree, we can optimize counting
    const leftHeight = getFullTreeHeight(root.left);
    const rightHeight = getFullTreeHeight(root.right);
    
    // If heights are equal, it's a perfect full tree
    if (leftHeight === rightHeight) {
        return Math.pow(2, leftHeight + 1) - 1;
    }
    
    // Otherwise, use recursive approach
    return 1 + countNodesFullTree(root.left) + countNodesFullTree(root.right);
}

2. Space-Efficient Validation

function spaceEfficientFullTreeCheck(root) {
    // Use iterative approach to avoid stack overflow in deep trees
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        
        if (node === null) continue;
        
        // Check if node has 0 or 2 children
        const hasZeroChildren = (node.left === null && node.right === null);
        const hasTwoChildren = (node.left !== null && node.right !== null);
        
        if (!(hasZeroChildren || hasTwoChildren)) {
            return false;
        }
        
        // Add children to stack for processing
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
    
    return true;
}

3. Batch Operations

function batchInsertFullTree(root, values) {
    // Insert multiple values efficiently maintaining full tree property
    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 (node.left === null && i < values.length) {
            node.left = new TreeNode(values[i++]);
        }
        
        // Insert right child if needed
        if (node.right === null && i < values.length) {
            node.right = new TreeNode(values[i++]);
        }
        
        // Add 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 Full Binary Tree

function isFullBinaryTree(root) {
    if (root === null) return true;
    
    // Leaf node - valid full tree property
    if (root.left === null && root.right === null) {
        return true;
    }
    
    // Internal node must have both children
    if (root.left !== null && root.right !== null) {
        return isFullBinaryTree(root.left) && isFullBinaryTree(root.right);
    }
    
    // Node has only one child - not full tree
    return false;
}

2. Count Nodes in Full Tree

function countFullTreeNodes(root) {
    if (root === null) return 0;
    
    // Leaf node
    if (root.left === null && root.right === null) {
        return 1;
    }
    
    // Internal node with two children
    return 1 + countFullTreeNodes(root.left) + countFullTreeNodes(root.right);
}

3. Find Maximum Height of Full Tree

function maxFullTreeHeight(root) {
    if (root === null) return -1;
    
    const leftHeight = maxFullTreeHeight(root.left);
    const rightHeight = maxFullTreeHeight(root.right);
    
    return 1 + Math.max(leftHeight, rightHeight);
}

Best Practices

1. Consistent Node Validation

Always check that nodes have either 0 or 2 children for full tree property.

2. Proper Tree Construction

When building full trees, ensure every internal node has exactly two children.

3. Efficient Memory Usage

Use iterative approaches for validation to avoid stack overflow in large trees.

4. Edge Case Handling

Handle empty trees, single nodes, and leaf-only trees correctly.

Key Takeaways

  1. Full Tree Definition: Every node has 0 or 2 children
  2. Structure Property: All internal nodes have exactly two children
  3. Mathematical Relationships: Height and node count have predictable patterns
  4. Algorithm Foundation: Forms basis for many tree algorithms
  5. Real-World Applications: Expression parsing, Huffman coding, file systems

Full binary trees are essential data structures that provide predictable behavior and mathematical properties useful in algorithm design, compiler construction, and many other computer science applications.

← PreviousComplete Binary TreeNext →Construct Tree from Traversals