Learning Journal

2/28/2024

Binary Tree Level Order Traversal

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function levelOrder(root: TreeNode | null): number[][] {
    if(root === null) return [];

    const queue:(TreeNode|null)[] = [root, null];
    const result:number[][] = [];

    let p = 0;

    let level:number[] = [];

    while(p < queue.length) {
        if(queue[p] === null) {
            result.push([...level]);
            level = [];

            if(p !== queue.length - 1)
                queue.push(null);
            
            p++;
            continue;
        }

        level.push(queue[p].val);

        if(queue[p].left !== null)
            queue.push(queue[p].left);
        
        if(queue[p].right !== null)
            queue.push(queue[p].right);

        p++;
    }

    return result;
};/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function levelOrder(root: TreeNode | null): number[][] {
    if(root === null) return [];

    const queue:(TreeNode|null)[] = [root, null];
    const result:number[][] = [];

    let p = 0;

    let level:number[] = [];

    while(p < queue.length) {
        if(queue[p] === null) {
            result.push([...level]);
            level = [];

            if(p !== queue.length - 1)
                queue.push(null);
            
            p++;
            continue;
        }

        level.push(queue[p].val);

        if(queue[p].left !== null)
            queue.push(queue[p].left);
        
        if(queue[p].right !== null)
            queue.push(queue[p].right);

        p++;
    }

    return result;
};

THE PROBLEM

My approach to this problem is using an array arr and a pointer p to mimic a queue. Then, I traverse the tree using breadth-first-search to add tree nodes to the queue and separate each level by null. There is another array named level to collect the values, then, when the pointer p reaches null, all content of level will be copied to the array result to return.

There is another approach that is faster, which uses 2 arrays, current and next to store the values of the current level and next level. You push the current to the array result while adding elements to the next array.

Revised by ChatGPT

My solution for this problem employs a breadth-first search approach using a simulated queue with an array queue and a pointer p. The algorithm traverses the tree level by level and uses null as a marker to separate each level.

An array level is used to collect the values of the current level.
When the pointer p encounters null, it indicates the end of a level. The contents of level are then copied to the result array, and level is reset for the next level.
If p is not at the end of the queue, a new null marker is added to indicate the end of the next level.

An alternative, more efficient approach uses two arrays, current and next, to store the values of the current and next levels, respectively. After processing all nodes in the current level, the contents are moved to the result array, and next becomes the new current level.