# in-order traverse and binary search

• Hi,
1 Inorder-traverse
time complexity: O(n)
space complexity: O(n) + O(logn)

``````int kthSmallest(TreeNode* root, int k) {
vector<int> array;
DFS(root, array);
return array[k - 1];
}

void DFS(TreeNode* root, vector<int>& array) {
if (root) {
DFS(root->left, array);
array.push_back(root->val);
DFS(root->right, array);
}
}
``````

no-brain solution. Just use inorder property to get a sorted array and index the desired entry

2.Optimization
time complexity:
average: O(nlogn)
worst: O(n^2)

``````int kthSmallest(TreeNode* root, int k) {
int count = countNode(root->left);
if (k == count + 1) return root->val;
if (k < count + 1) return kthSmallest(root->left, k);
else return kthSmallest(root->right, k - count - 1);
}

int countNode(TreeNode* root) {
if (root == nullptr) {
return 0;
}

return countNode(root->left) + countNode(root->right) + 1;
}
``````

The first method requires us to traverse the entire tree, which is unnecessary. We can count how many nodes in a leftsubtree to decide the kth element may sit in left subtree or right subtree.
Also I think this solution is for the follow-up. If we modify the tree very often and call kthsmallest frequently. We can add a "count" field to each node and update it in each dynamic operation. In this way kthsmallest can be done in o(lgN);

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