897. Increasing Order Search Tree

leetcode.com/problems/increasing-order-search-tree/

Increasing Order Search Tree - LeetCode

 

 

Approach 1: In-Order Traversal

class Solution {    
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> vals = new ArrayList();
        inorder(root, vals);
        TreeNode ans = new TreeNode(0), cur = ans;
        for (int v: vals) {
            cur.right = new TreeNode(v);
            cur = cur.right;
        }
        return ans.right;
    }

    public void inorder(TreeNode node, List<Integer> vals) {
        if (node == null) return;
        inorder(node.left, vals);
        vals.add(node.val);
        inorder(node.right, vals);
    }
}

Time Complexity: O(N), where N is the number of nodes in the given tree.

Space Complexity: O(N), the size of the answer.

 

 

Approach 2: Traversal with Relinking

class Solution {
    TreeNode cur;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode ans = new TreeNode(0);
        cur = ans;
        inorder(root);
        return ans.right;
    }

    public void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        node.left = null;
        cur.right = node;
        cur = node;
        inorder(node.right);
    }
}

Time Complexity: O(N), where NN is the number of nodes in the given tree.

Space Complexity: O(H) in additional space complexity, where H is the height of the given tree, and the size of the implicit call stack in our in-order traversal.