Learning Journal

2/7/2024

Closest Nodes Queries in a Binary Search Tree - 3rd attempt

Tags: algorithms leetcode binary_search_tree

/**
 * 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 closestNodes(root: TreeNode | null, queries: number[]): number[][] {
    const tree = new Tree(root);
    const result: number[][] = [];

    for(let i = 0; i < queries.length; i++) {
        result.push(tree.search(queries[i]));
    }

    return result;
};

class Tree {
    private arr:number[] = [];
    constructor(node:TreeNode) {
        this.flatten(node);
    }

    private flatten(node:TreeNode) {
        if(node === null) return;

        this.flatten(node.left);
        this.arr.push(node.val);
        this.flatten(node.right);
    }

    search(val:number):number[] {
        let lo = 0, hi = this.arr.length - 1;
        let mid = Math.floor((lo + hi)/2);

        while(lo <= hi) {
            if(this.arr[mid] < val) {
                lo = mid + 1;
                mid = Math.floor((lo + hi)/2);
            }
            else if(this.arr[mid] > val) {
                hi = mid - 1;
                mid = Math.floor((lo + hi)/2);
            }
            else {
                return [val, val];
            }
        }
  
        const min = hi >= 0? this.arr[hi] : -1;
        const max = lo < this.arr.length? this.arr[lo]: -1;

        return [min, max];
    }
}/**
 * 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 closestNodes(root: TreeNode | null, queries: number[]): number[][] {
    const tree = new Tree(root);
    const result: number[][] = [];

    for(let i = 0; i < queries.length; i++) {
        result.push(tree.search(queries[i]));
    }

    return result;
};

class Tree {
    private arr:number[] = [];
    constructor(node:TreeNode) {
        this.flatten(node);
    }

    private flatten(node:TreeNode) {
        if(node === null) return;

        this.flatten(node.left);
        this.arr.push(node.val);
        this.flatten(node.right);
    }

    search(val:number):number[] {
        let lo = 0, hi = this.arr.length - 1;
        let mid = Math.floor((lo + hi)/2);

        while(lo <= hi) {
            if(this.arr[mid] < val) {
                lo = mid + 1;
                mid = Math.floor((lo + hi)/2);
            }
            else if(this.arr[mid] > val) {
                hi = mid - 1;
                mid = Math.floor((lo + hi)/2);
            }
            else {
                return [val, val];
            }
        }
  
        const min = hi >= 0? this.arr[hi] : -1;
        const max = lo < this.arr.length? this.arr[lo]: -1;

        return [min, max];
    }
}

PROBLEM

Some notes over this attempt.

The reason that you should stop the loop when lo and hi cross over each other instead of meeting each other is that the second choice requires a lot more handling than the first one. If you stop when lo === hi, you need to take care of the scenario when they both point to the correct value. However, when you stop at lo > hi, you are 100% sure that there is no such value.
The in-order traverse using recursion is more complex than I thought. First, you go all the way to the left. When you reach the end, you go back 1 step, push the most left node's value to the array, go to the right node, and do the same thing over again. What is the "same thing"? It is that you need to go all the way to the left again. When you reach the end, go back 1 step, push the most left node's value to the array, go to the right node. It's kind of mind-bending if you don't think about it recursively. So, what is the recursive way of thinking? You know that if it is the leave, the algorithm will go to the left, reach null, push the node's value, go to the right, reach null, go back, and finish. So, it works for a leave (or a tree of 1 node). How about a tree of 3 nodes? It goes to the left, does the thing like it does with the tree of one node, goes back, prints the root's value, goes right, does the thing with the tree of one node, goes back, and finishes. So, we know that it works for the tree of one node and the tree of 3 nodes. For the tree of 3 levels, it still works the same. That's why we know it works.

Revised by ChatGPT

This implementation addresses the problem of finding the closest nodes in a binary search tree (BST) for a given set of queries. It does so by leveraging the properties of BST and binary search algorithm. Here's an overview of the key components and insights from this approach:

Stopping Condition in Binary Search: the binary search within the search method is designed to stop when lo > hi. This approach simplifies the logic by avoiding the need for additional handling that would be required if we stopped when lo === hi. Specifically, it eliminates the need to deal with scenarios where lo and hi could point to the correct value. When the loop exits with lo > hi, it is guaranteed that the search value does not exist in the array, and the positions of lo and hi can be used to find the closest values.
In-order Traversal Complexity: The method flatten, which performs an in-order traversal of the BST, is highlighted for its recursive nature and complexity. An in-order traversal visits the left subtree, the root, and then the right subtree. This method is particularly well-suited for BSTs because it processes the nodes in ascending order. The recursive approach simplifies the traversal by ensuring that each subtree is fully processed before moving on to the next. This method is efficient for flattening the BST into a sorted array, which is then used for binary search.

The recursive logic is based on the principle that the algorithm functions correctly for a single node (leaf) by visiting the left child (null), processing the node, and then visiting the right child (null).
For a tree with more nodes, the process is the same: it recursively flattens the left subtree, processes the current node, and then recursively flattens the right subtree. This ensures that all nodes are processed in their ascending order.
Understanding the recursive in-order traversal requires viewing each node as the root of its subtree, where the algorithm applies equally, ensuring that the entire tree is flattened correctly. This solution effectively prepares the BST data into a form that allows efficient queries for closest nodes using binary search, capitalizing on the sorted nature of the in-order traversal output.