# An iterative solution in JAVA, is it correct?

• Generate from 1 to n and build ith iteration based on (i-1)th trees.

Basically given node i is the largest node so far, for each (i-1)th subtree:

• add node i at root and attach (i-1)th trees to its left
• find the largest node in (i-1)th trees, add node i to its right
• find the largest node in (i-1)th trees, add it to node i's right, and add node i to its parent's right
• handle duplicated case when the largest node in (i-1)th trees is root

It didn't pass OJ at n=4 but I checked the result is correct except for the ordering in the sequence.

Is it correct for n>4? and How to analyze the time complexity?

``````public class Solution {
public List<TreeNode> generateTrees(int n) {
List<TreeNode> res = new ArrayList<TreeNode>();
TreeNode newNode = null;
if(n<=0){
return res;
}
for(int i = 1; i <= n; i++){
int size = res.size();
if(size==0){
newNode = new TreeNode(i);
}else{
for(int j = 0; j < size; j++){
TreeNode prev = res.remove(0);
TreeNode curr;
}
}
}
return res;
}

private TreeNode addToMaxBelow(int i, TreeNode prev){
TreeNode newNode = new TreeNode(i);
TreeNode prevRoot = copyTree(prev);
TreeNode max = getMax(prevRoot);
if(max==null) return null;
max.right = newNode;
return prevRoot;
}

private TreeNode addToMaxAbove(int i, TreeNode prev){
TreeNode newNode = new TreeNode(i);
TreeNode prevRoot = copyTree(prev);
TreeNode maxParent = getMaxParent(prevRoot);
if(maxParent==null) return null;
newNode.left = maxParent.right;
maxParent.right = newNode;
return prevRoot;
}

private TreeNode addToRoot(int i, TreeNode prev){
TreeNode newNode = new TreeNode(i);
TreeNode prevRoot = copyTree(prev);
newNode.left = prevRoot;
return newNode;
}

private TreeNode getMax(TreeNode root){
if(root==null) return root;
TreeNode curr = root;
while(curr.right!=null){
curr = curr.right;
}
return curr;
}

private TreeNode getMaxParent(TreeNode root){
if(root==null) return root;
TreeNode prev = null;
TreeNode curr = root;
while(curr.right!=null){
prev = curr;
curr = curr.right;
}
return prev;
}

private TreeNode copyTree(TreeNode root){
if(root==null) return null;
TreeNode newRoot = new TreeNode(root.val);
newRoot.left = copyTree(root.left);
newRoot.right = copyTree(root.right);
return newRoot;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.