99클럽 코테 스터디 18일차 TIL - Increasing Order Search Tree

---

// Interface for a binary tree node.
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}

// Function to create a new TreeNode with a specific value.
function createTreeNode(val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode {
    return {
        val: val,
        left: left,
        right: right
    };
}

let previousNode: TreeNode | null; // Variable to keep track of the previously processed node.

// Function that takes a binary search tree and rearranges it so that it becomes a strictly
// increasing order tree where each node only has a right child following an in-order traversal
// of the tree.
function increasingBST(root: TreeNode): TreeNode {
    const dummyNode: TreeNode = createTreeNode(0); // Create a dummy node that will act as the "previous node" of the first node in the in-order traversal.
    previousNode = dummyNode; // Initialize previousNode with the dummy node.

    // Start the in-order traversal and rearrange the tree.
    inOrderTraversal(root); 

    // Return the right child of the dummy node, which is the new root of the rearranged tree.
    return dummyNode.right!;
}

// Helper function that performs a depth-first search (DFS) in-order traversal of the binary tree.
function inOrderTraversal(currentNode: TreeNode | null): void {
    if (currentNode === null) return; // If the current node is null, do nothing and return.

    // First, traverse the left subtree (in-order).
    inOrderTraversal(currentNode.left);

    // Assign the current node to the right child of the previous node.
    if (previousNode) previousNode.right = currentNode; 

    // The current node should not have a left child in the rearranged tree.
    currentNode.left = null;

    // Update the previousNode to be the current node after processing it.
    previousNode = currentNode;

    // Next, traverse the right subtree (in-order).
    inOrderTraversal(currentNode.right);
}