230-trees-problem-23.md

Trees Problem 23

LeetCode: https://leetcode.com/problems/kth-largest-element-in-a-stream/ Difficulty: Medium

Problem

Solve this trees problem efficiently.

Brute Force Approach

function solve(root) {
    // Level order traversal with queue
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length) {
        const level = [];
        const size = queue.length;
        
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            level.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(level);
    }
    return result;
}

⏱️ Time: O(n²) or O(n³)
💾 Space: O(n)

Optimal Approach

function solve(root) {
    // DFS recursive approach
    function dfs(node, depth) {
        if (!node) return;
        
        if (depth === result.length) {
            result.push([]);
        }
        
        result[depth].push(node.val);
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }
    
    const result = [];
    dfs(root, 0);
    return result;
}

⏱️ Time: O(n) or O(n log n)
💾 Space: O(n) or O(1)

Visual Diagram

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

Traversal:
Inorder: 1,2,3,4,5,6,7
Preorder: 4,2,1,3,6,5,7
Postorder: 1,3,2,5,7,6,4

---

Visit LeetCode for full problem description.