Increasing Order Search Tree

LeetCode Q 897 - Increasing Order Search Tree

Given a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

Note:

• The number of nodes in the given tree will be between 1 and 100.
• Each node will have a unique integer value from 0 to 1000.

Solution:

Soultion 1:

Code:

List<Integer> list;
public TreeNode increasingBST(TreeNode root) {
  if (root == null) return null;
  
  list = new ArrayList<>();
  
  dfs (root);
  
  TreeNode newRoot = new TreeNode(list.get(0));
  TreeNode curr = newRoot;
  for (int i = 1; i < list.size(); i++) {
    TreeNode n = new TreeNode(list.get(i));
    curr.right = n;
    curr = n;
  }
  
  return newRoot;
}

private void dfs(TreeNode root) {
  if (root == null) return;
  dfs(root.left);
  list.add(root.val);
  dfs(root.right);
}

Soultion 2: More concise version

Code:

TreeNode curr = null;
public TreeNode increasingBST(TreeNode root) {
  if (root == null) return root;
  
  TreeNode dummy = curr = new TreeNode (-1);

  dfs(root);

  return dummy.right;
}

private void dfs(TreeNode root) {
  if (root == null) return;

  dfs(root.left);

  curr.right = root; 
  curr = curr.right;

  dfs(root.right);

  root.left = null;
}