Tree Height and Depth

Overview

Tree height and depth are fundamental concepts in tree data structures that measure different aspects of tree structure. Understanding these concepts is crucial for analyzing tree performance, calculating path lengths, and solving various tree algorithm problems.

Key Definitions

Depth of a Node

The depth of a node is the number of edges from the root to that node. The root node has depth 0.

Height of a Node

The height of a node is the number of edges in the longest path from that node to a leaf node. The height of a leaf node is 0.

Height of a Tree

The height of a tree is the height of its root node, or equivalently, the maximum depth of any node in the tree.

Algorithm Implementation

Calculating Height (Recursive Approach)

function calculateHeight(root) {
    if (root === null) return -1; // Height of empty tree is -1
    
    const leftHeight = calculateHeight(root.left);
    const rightHeight = calculateHeight(root.right);
    
    return 1 + Math.max(leftHeight, rightHeight);
}

Calculating Depth (Recursive Approach)

function calculateDepth(root, targetNode, currentDepth = 0) {
    if (root === null) return -1; // Node not found
    
    if (root === targetNode) return currentDepth;
    
    const leftDepth = calculateDepth(root.left, targetNode, currentDepth + 1);
    if (leftDepth !== -1) return leftDepth;
    
    const rightDepth = calculateDepth(root.right, targetNode, currentDepth + 1);
    return rightDepth;
}

Calculating Height Iterative Approach (Level Order)

function calculateHeightIterative(root) {
    if (root === null) return -1;
    
    const queue = [root];
    let height = 0;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        // Process all nodes at current level
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        height++; // Increment height for each level processed
    }
    
    return height - 1; // Subtract 1 to get actual height (0-indexed)
}

Relationship Between Height and Depth

Key Relationships

1. For any node: Height = Maximum depth of all leaf nodes in its subtree
2. For root node: Height = Maximum depth of any node in tree
3. For leaf nodes: Height = 0, Depth = Distance from root

Example Tree Structure

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

Calculations for Each Node:

• Node 1 (Root): Depth = 0, Height = 2
• Node 2: Depth = 1, Height = 1
• Node 3: Depth = 1, Height = 1
• Node 4: Depth = 2, Height = 0 (Leaf)
• Node 5: Depth = 2, Height = 0 (Leaf)
• Node 6: Depth = 2, Height = 0 (Leaf)
• Node 7: Depth = 2, Height = 0 (Leaf)

Common Variations and Calculations

Maximum Depth of Binary Tree

function maxDepth(root) {
    if (root === null) return 0;
    
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    
    return 1 + Math.max(leftDepth, rightDepth);
}

Minimum Depth of Binary Tree

function minDepth(root) {
    if (root === null) return 0;
    
    // If leaf node, return 1
    if (root.left === null && root.right === null) return 1;
    
    // If one child is missing, go to the existing child
    if (root.left === null) return 1 + minDepth(root.right);
    if (root.right === null) return 1 + minDepth(root.left);
    
    // Both children exist, take minimum
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

Diameter of Binary Tree (Height-based)

function diameterOfBinaryTree(root) {
    let diameter = 0;
    
    function calculateHeight(node) {
        if (node === null) return 0;
        
        const leftHeight = calculateHeight(node.left);
        const rightHeight = calculateHeight(node.right);
        
        // Diameter at current node = leftHeight + rightHeight
        diameter = Math.max(diameter, leftHeight + rightHeight);
        
        return 1 + Math.max(leftHeight, rightHeight);
    }
    
    calculateHeight(root);
    return diameter;
}

Time and Space Complexity

| Operation | Time Complexity | Space Complexity |

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

| Height Calculation (Recursive) | O(n) | O(h) |

| Height Calculation (Iterative) | O(n) | O(w) |

| Depth Calculation | O(n) | O(h) |

Where:

• n = number of nodes in tree
• h = height of tree (recursion stack space)
• w = maximum width of tree (queue space)

Common Mistakes to Avoid

1. Incorrect Height Definition

// ❌ Wrong - Confusing height and depth definitions
function wrongHeight(root) {
    if (root === null) return 0; // Should be -1 for empty tree
    
    const left = wrongHeight(root.left);
    const right = wrongHeight(root.right);
    
    return Math.max(left, right) + 1; // Should be left + 1 or right + 1
}

2. Missing Null Checks

// ❌ Wrong - Not handling null nodes properly
function incompleteHeight(root) {
    const left = calculateHeight(root.left);
    const right = calculateHeight(root.right);
    
    return 1 + Math.max(left, right); // Will fail if root is null
}

3. Misunderstanding Leaf Node Definition

// ❌ Wrong - Not properly identifying leaf nodes
function wrongLeafCheck(node) {
    if (node === null) return 0;
    
    // This incorrectly assumes all nodes have children
    if (node.left === null && node.right === null) {
        return 0; // Should return 0 for leaf nodes
    }
    
    return 1 + Math.max(calculateHeight(node.left), calculateHeight(node.right));
}

Comparison with Related Concepts

Depth vs Height

| Concept | Definition | When Used |

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

| Depth | Distance from root to node | When finding specific node's position |

| Height | Longest path from node to leaf | When analyzing tree structure |

Maximum vs Minimum Depth

| Type | Description | Use Case |

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

| Maximum Depth | Deepest leaf node in tree | Tree balancing analysis |

| Minimum Depth | Shortest path to leaf | Finding minimum height |

Practical Applications

1. Balanced Tree Analysis

function isBalanced(root) {
    function checkBalance(node) {
        if (node === null) return 0;
        
        const leftHeight = checkBalance(node.left);
        if (leftHeight === -1) return -1; // Unbalanced subtree
        
        const rightHeight = checkBalance(node.right);
        if (rightHeight === -1) return -1; // Unbalanced subtree
        
        const heightDiff = Math.abs(leftHeight - rightHeight);
        if (heightDiff > 1) return -1; // Not balanced
        
        return 1 + Math.max(leftHeight, rightHeight);
    }
    
    return checkBalance(root) !== -1;
}

2. Tree Serialization/Deserialization

function serialize(root) {
    const result = [];
    
    function dfs(node) {
        if (node === null) {
            result.push("null");
            return;
        }
        
        result.push(node.val);
        dfs(node.left);
        dfs(node.right);
    }
    
    dfs(root);
    return result.join(",");
}

3. Tree Level Analysis

function levelOrderWithHeight(root) {
    if (root === null) return [];
    
    const levels = [];
    const queue = [root];
    let currentLevel = 0;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        levels[currentLevel] = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            levels[currentLevel].push({
                value: node.val,
                depth: currentLevel,
                height: calculateHeight(node) // Height of this node
            });
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        currentLevel++;
    }
    
    return levels;
}

Performance Considerations

1. Space Optimization

// Iterative approach for better space usage in deep trees
function iterativeHeight(root) {
    if (root === null) return -1;
    
    let maxDepth = 0;
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        maxDepth++;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    
    return maxDepth - 1; // Convert to height
}

2. Early Termination

function optimizedHeight(root) {
    if (root === null) return -1;
    
    // For balanced trees, we can optimize by checking if tree is already balanced
    const leftHeight = calculateHeight(root.left);
    const rightHeight = calculateHeight(root.right);
    
    return 1 + Math.max(leftHeight, rightHeight);
}

Common Interview Questions

1. Find Maximum Depth of Binary Tree

function maxDepth(root) {
    if (root === null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

2. Find Minimum Depth of Binary Tree

function minDepth(root) {
    if (root === null) return 0;
    
    if (root.left === null) return 1 + minDepth(root.right);
    if (root.right === null) return 1 + minDepth(root.left);
    
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

3. Check if Tree is Height Balanced

function isBalanced(root) {
    function checkBalance(node) {
        if (node === null) return 0;
        
        const left = checkBalance(node.left);
        if (left === -1) return -1;
        
        const right = checkBalance(node.right);
        if (right === -1) return -1;
        
        if (Math.abs(left - right) > 1) return -1;
        
        return 1 + Math.max(left, right);
    }
    
    return checkBalance(root) !== -1;
}

Best Practices

1. Consistent Definitions

Always define whether you're measuring height from root (0-indexed) or from leaf (1-indexed).

2. Edge Case Handling

Always handle:

• Empty trees (height = -1 or 0)
• Single node trees
• Null nodes

3. Efficient Implementation

Choose between:

• Recursive (cleaner, easier to understand)
• Iterative (better for very deep trees - avoids stack overflow)

Key Takeaways

1. Height vs Depth: Height measures from node to leaf, depth measures from root to node
2. Tree Balance: Height difference between subtrees determines balance
3. Practical Use: Essential for tree algorithms, serialization, and optimization problems
4. Performance: O(n) time complexity for most height calculations

Understanding tree height and depth is fundamental to solving complex tree problems, particularly in competitive programming, system design, and algorithm analysis where tree structure properties are crucial for optimal solutions.