897. Increasing Order Search Tree

EasyStackTreeDepth-First SearchBinary Search TreeBinary Tree
Leetcode Link

Problem Description

The problem statement presents a binary search tree (BST) and asks for a transformation of this BST into a new tree that is essentially a linked list in ascending order. In other words, the task is to rearrange the tree such that it maintains the in-order sequence of values, where every node only has a right child, effectively eliminating all the left children. The leftmost node of the original BST should become the new root of the so-called 'flattened' tree.

Intuition

The solution leverages the property of BSTs where an in-order traversal yields the nodes in ascending order. The concept here is to perform an in-order Depth-First Search (DFS) traversal, and as we visit each node, we rearrange the pointers to create the 'right-skewed' tree desired for the problem.

The intuition behind the approach can be broken down into steps:

  1. Initialize a 'dummy' node as a precursor to the new root to make attachment easier.
  2. Start the in-order DFS from the root of the original BST.
  3. As the in-order DFS visits the nodes, adjust pointers such that each visited node becomes the right child of the previously visited node ('prev').
    • The current node's left child is set to None.
    • The current node's right child becomes the entry point for the next nodes that are yet to be visited in the DFS.
  4. The 'prev' node, initialized as the dummy node, is updated in each step to the current node.
  5. After the traversal, the right child of the dummy node (which was our starting point) now points to the new root of the in-order rearranged tree.
  6. The leftmost node from the original tree is now acting as the root of this reordered straight line tree.

This approach ensures that every node, except for the first (new root), will only have a single right child, fulfilling the condition of having no left child and at most one right child.

Learn more about Stack, Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

How many times is a tree node visited in a depth first search?

Solution Approach

The solution implements an in-order traversal to process nodes of a binary search tree (BST) in the ascending order of their values. An in-order traversal visits nodes in the "left-root-right" sequence, which aligns with the BST property that left child nodes have smaller values than their parents, and right child nodes have larger values.

Here's a breakdown of the key parts of the solution:

  • An inner function dfs (short for Depth-First Search) is defined, which recursively traverses the BST in an in-order fashion. It helps us visit each node in the required sequence to rearrange the tree.

  • A 'dummy' node is initiated before the traversal begins. This node serves as a placeholder to easily point to the new tree's root after the rearrangement is complete.

  • The prev variable points to the last processed node in the in-order sequence. Initially, it's set to the 'dummy' node to start the rearrangement process.

  • During each call to dfs:

    1. The left subtree is processed, ensuring that all smaller values have already been visited before we rearrange the current node.
    2. The current node (root) is detached from its left child by setting it to None.
    3. The right attribute of the prev node is set to the current node, effectively 'flattening' the tree by making the current node the next element in the list.
    4. The prev variable is updated to the current node, preparing it to link to the next node in the traversal.
    5. The right subtree is processed, continuing the in-order traversal.

  • Due to the nonlocal keyword usage, the prev variable retains its value across different dfs invocations.

  • After completing the DFS, the right child of the 'dummy' node is returned. This now points to the leftmost node of the original BST, which is the new root of the restructured 'tree' (now resembling a linked list).

  • The end result is that all nodes are rearranged into a straight line, each having no left child, and only one right child, reflecting an in-order traversal of the original BST.

In summary, the solution uses a recursive in-order DFS traversal, pointer manipulation, and a 'dummy' placeholder node to create a modified tree that satisfies the specific conditions. It efficiently flattens the BST into a single right-skewed path that represents the ascending order of the original tree's values.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Example Walkthrough

Let's illustrate the solution approach with an example. Consider the following BST:

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

According to the in-order traversal, the nodes are visited in the order: 1, 2, 3, 4, 5, 6, 7. We will flatten this BST to a right-skewed tree.

Here's step by step how the algorithm will work on this BST:

  1. Initialize a dummy node as a precursor to the new root to make the attachment of nodes easier.

    • Let's say dummy.val is 0 for illustration purposes.

  2. Start in-order DFS with the dummy node's prev pointing to it.

  3. Visit the leftmost node, which is 1. At this point:

    • Set prev.right = node 1, disconnect node 1 from its left (none in this case).
    • Update prev to be node 1.

  4. Visit node 2, the parent of node 1:

    • Since node 1 right is null, set node 1.right = node 2 and disconnect node 2 from its left (which was node 1).
    • Update prev to be node 2.

  5. Proceed to node 3 by visiting the right subtree of node 2:

    • Set node 2.right = node 3 and disconnect node 3 from its left (none).
    • Update prev to be node 3.

  6. Continue with node 4 (root of the original BST) similarly:

    • Set node 3.right = node 4 and disconnect node 4 from its left (which was node 2).
    • Update prev to be node 4.

  7. Move to node 5 through the left part of the right subtree of node 4:

    • Set node 4.right = node 5 and disconnect node 5 from its left (none).
    • Update prev to be node 5.

  8. Node 6 is processed next:

    • Set node 5.right = node 6 and disconnect node 6 from its left (which was node 5).
    • Update prev to be node 6.

  9. Finally, visit node 7:

    • Set node 6.right = node 7 and disconnect node 7 from its left (none).
    • Update prev to be node 7.

  10. At the end of this DFS process, the BST has been turned into a right-skewed list:

10 - 1 - 2 - 3 - 4 - 5 - 6 - 7
  1. The dummy node's right child (0's right child) is node 1, so this is the new root of the flattened tree:
11 - 2 - 3 - 4 - 5 - 6 - 7

We've now flattened the original BST to a linked list in ascending order following the in-order sequence of the BST. Each node has no left child and only one right child.

Solution Implementation

1class TreeNode:
2    # TreeNode class definition remains the same
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def increasingBST(self, root: TreeNode) -> TreeNode:
10        # Helper function to perform in-order traversal
11        def in_order_traversal(node):
12            # Base case: if node is None, return
13            if not node:
14                return
15          
16            # Traverse the left subtree
17            in_order_traversal(node.left)
18          
19            # Visit the current node: 
20            # Since we are rearranging the tree into a right-skewed tree,
21            # we make the previously visited node's right point to the current node
22            self.prev.right = node
23          
24            # Disconnect the current node's left child
25            node.left = None
26          
27            # Update the previous node to be the current node
28            self.prev = node
29          
30            # Traverse the right subtree
31            in_order_traversal(node.right)
32
33        # Dummy node to start the right-skewed tree
34        dummy = TreeNode()
35        # 'prev' initially points to the dummy node
36        self.prev = dummy
37      
38        # Perform in-order traversal; this will rearrange the nodes
39        in_order_traversal(root)
40      
41        # The right child of the dummy node is the root of the modified tree
42        return dummy.right
43
1class Solution {
2    // 'prev' will be used to keep track of the previous node in inorder traversal.
3    private TreeNode previousNode;
4
5    public TreeNode increasingBST(TreeNode root) {
6        // 'dummyNode' will act as a placeholder to the beginning of the resulting increasing BST.
7        TreeNode dummyNode = new TreeNode(0);
8        previousNode = dummyNode;
9      
10        // Perform the 'inorder' traversal starting from the root.
11        inorderTraversal(root);
12      
13        // Return the right child of the dummy node, which is the real root of the increasing BST.
14        return dummyNode.right;
15    }
16
17    // The 'inorderTraversal' function recursively traverses the tree in an inorder fashion.
18    private void inorderTraversal(TreeNode node) {
19        // If the current node is 'null', we have reached the end and should return.
20        if (node == null) {
21            return;
22        }
23      
24        // Recurse on the left subtree.
25        inorderTraversal(node.left);
26      
27        // During the inorder traversal, we reassign the rights of the 'previousNode' to the current 'node'
28        // and nullify the left child to adhere to increasing BST rules.
29        previousNode.right = node;
30        node.left = null;
31      
32        // Update 'previousNode' to the current node.
33        previousNode = node;
34      
35        // Recurse on the right subtree.
36        inorderTraversal(node.right);
37    }
38}
39
1// Declaration for a binary tree node.
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6    // Constructor for a new empty TreeNode.
7    TreeNode() : val(0), left(nullptr), right(nullptr) {}
8    // Constructor for a TreeNode with a specific value.
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    // Constructor for a TreeNode with a value and specified left and right children.
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    TreeNode* previousNode; // Node to keep track of the previously processed node.
17
18    // Takes a binary search tree and rearranges it so that it becomes a strictly increasing order tree
19    // where each node only has a right child following an in-order traversal of the tree.
20    TreeNode* increasingBST(TreeNode* root) {
21        TreeNode* dummyNode = new TreeNode(0); // Create a dummy node that acts as the previous node of the first node in the in-order traversal.
22        previousNode = dummyNode; // Initialize previousNode with the dummy node.
23      
24        inOrderTraversal(root); // Start the in-order traversal and rearrange the tree.
25      
26        // Return the right child of the dummy node, which is the new root of the rearranged tree.
27        return dummyNode->right;
28    }
29
30    // Helper function that performs DFS in-order traversal of the binary tree.
31    void inOrderTraversal(TreeNode* currentNode) {
32        if (!currentNode) return; // If the current node is null, return.
33      
34        // Traverse the left subtree first (in-order).
35        inOrderTraversal(currentNode->left);
36      
37        previousNode->right = currentNode; // Assign the current node to the right child of the previous node.
38        currentNode->left = nullptr; // The current node should not have a left child in the rearranged tree.
39        previousNode = currentNode; // Update the previousNode to be the current node after processing it.
40      
41        // Traverse the right subtree next (in-order).
42        inOrderTraversal(currentNode->right);
43    }
44};
45
1// Interface for a binary tree node.
2interface TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6}
7
8// Function to create a new TreeNode with a specific value.
9function createTreeNode(val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode {
10    return {
11        val: val,
12        left: left,
13        right: right
14    };
15}
16
17let previousNode: TreeNode | null; // Variable to keep track of the previously processed node.
18
19// Function that takes a binary search tree and rearranges it so that it becomes a strictly
20// increasing order tree where each node only has a right child following an in-order traversal
21// of the tree.
22function increasingBST(root: TreeNode): TreeNode {
23    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.
24    previousNode = dummyNode; // Initialize previousNode with the dummy node.
25
26    // Start the in-order traversal and rearrange the tree.
27    inOrderTraversal(root); 
28
29    // Return the right child of the dummy node, which is the new root of the rearranged tree.
30    return dummyNode.right!;
31}
32
33// Helper function that performs a depth-first search (DFS) in-order traversal of the binary tree.
34function inOrderTraversal(currentNode: TreeNode | null): void {
35    if (currentNode === null) return; // If the current node is null, do nothing and return.
36
37    // First, traverse the left subtree (in-order).
38    inOrderTraversal(currentNode.left);
39
40    // Assign the current node to the right child of the previous node.
41    if (previousNode) previousNode.right = currentNode; 
42
43    // The current node should not have a left child in the rearranged tree.
44    currentNode.left = null;
45
46    // Update the previousNode to be the current node after processing it.
47    previousNode = currentNode;
48
49    // Next, traverse the right subtree (in-order).
50    inOrderTraversal(currentNode.right);
51}
52
Not Sure What to Study? Take the 2-min Quiz๏ผš

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Time and Space Complexity

The time complexity of the code is O(n) where n is the number of nodes in the binary tree. This is because the solution involves performing a depth-first search (dfs) traversal of the tree, which visits each node exactly once.

The space complexity of the code is also O(n) in the worst-case scenario, which occurs when the binary tree is completely unbalanced (e.g., every node only has a left child, forming a linear chain). In this case, the recursion stack depth would be n. For balanced trees, the space complexity would be O(h) where h is the height of the tree, since the depth of recursion would only be as deep as the height of the tree.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ