Learning Journal

3/2/2024

Binary Tree Right Side View

/**
 * 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 rightSideView(root: TreeNode | null): number[] {
    if(root === null) return [];
    
    const arr: (TreeNode | null)[] = [root,null];
    const result:number[] = [];

    let p = 0;

    while (p < arr.length) {
        const curNode = arr[p];

        if(curNode === null) {
            result.push(arr[p-1].val);
            if(p !== arr.length - 1){
                arr.push(null);
            }
        }
        else {
            if(curNode.left)
                arr.push(curNode.left);
            
            if(curNode.right)
                arr.push(curNode.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 rightSideView(root: TreeNode | null): number[] {
    if(root === null) return [];
    
    const arr: (TreeNode | null)[] = [root,null];
    const result:number[] = [];

    let p = 0;

    while (p < arr.length) {
        const curNode = arr[p];

        if(curNode === null) {
            result.push(arr[p-1].val);
            if(p !== arr.length - 1){
                arr.push(null);
            }
        }
        else {
            if(curNode.left)
                arr.push(curNode.left);
            
            if(curNode.right)
                arr.push(curNode.right);
        }

        p++;
    }

    return result;
};

THE PROBLEM

This is my solution for this problem using queue approach. Basically, you iterate through the tree level by level. Just imagine at the end of each level, you reach a wall. So what is the right side view of this Binary Tree? Well, it includes the nodes right before you reach the wall.

So, I use breadth-first-search to mimic the scenario. First, you push the root node to the queue, then you push null to denote the wall, because right after the root node is the wall. Then, you use a pointer to travel through the queue, and push left child and right child of the current node to the queue. When you reach null, you know that you already push all of the node on the next level to the queue, so the next thing is null. Moreover, when you reach null, you know that the element right before it is the right side view of the tree, you push it to the result array.

Revised by ChatGPT

This problem requires us to find the right side view of a binary tree. The right side view is defined as the set of nodes visible when the tree is viewed from the right side.

To solve this problem, I used a breadth-first search (BFS) approach with a queue. The key idea is to traverse the tree level by level and capture the rightmost node at each level. Here's how the algorithm works:

Initialization: Start by adding the root node to the queue, followed by a null marker to denote the end of the first level.
Traversal: Use a pointer to iterate through the queue. For each non-null node, enqueue its left and right children (if they exist) to the queue.
Rightmost Node: When the pointer encounters a null marker, it means we've reached the end of the current level. The node immediately preceding the null marker is the rightmost node of that level, so we add it to the result array.
Next Level: After encountering a null marker, if there are more nodes in the queue (i.e., the next level is not empty), add another null marker to the end of the queue to mark the end of the next level.
Termination: The loop terminates when the pointer has processed all elements in the queue.

By following this approach, we ensure that we capture the rightmost node at each level, giving us the right side view of the binary tree.