# What's the time complexity of my Accepted Java Solution?

• I have this Accepted solution but I didn't figure out the time complexity of it. Could anyone help?

``````/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {

return findRoot(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
}

private TreeNode findRoot(int[] inorder, int inleft, int inright, int[] postorder, int postleft, int postright){

if(inleft > inright)return null; // base case

int rootVal = postorder[postright]; // the last node in postorder is always the root node
TreeNode root = new TreeNode(rootVal);

// find position of the root node in inorder array
int mid = 0;
for(int i=inleft; i<=inright; ++i){

if(inorder[i] == rootVal){
mid = i;
break;
}
}

int leftNum = mid - inleft; // number of nodes in left part

root.left = findRoot(inorder, inleft, mid-1, postorder, postleft, postleft+leftNum-1); // left subtree is on the left side of the root
root.right = findRoot(inorder, mid+1, inright, postorder, postleft+leftNum, postright-1); // right subtree is on the right side of the root

return root;
}
}``````

• It is not O(n) for sure. Probably O(n*logn) if the tree is balanced.

• I figure out the same algorithm with you!

• Your algorithm is O(nlogn) if the binary tree is balanced. Space complexity is the level of stack which is O(logn) if the tree is balanced.

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