function validateBst(root, min=-Infinity, max=Infinity) {
if (!root) return true;
if (root.value <= min || root.value > max) return false;
return validateBst(root.left, min, root.value) && validateBst(root.right,root.value, max)
}
Can someone clarify this for me...is this space plexity of this function O(log(n)) or O(d) - where d is the depth of the BST tree?
...can I classify them as the same thing?
function validateBst(root, min=-Infinity, max=Infinity) {
if (!root) return true;
if (root.value <= min || root.value > max) return false;
return validateBst(root.left, min, root.value) && validateBst(root.right,root.value, max)
}
Can someone clarify this for me...is this space plexity of this function O(log(n)) or O(d) - where d is the depth of the BST tree?
...can I classify them as the same thing?
Share Improve this question edited Jun 26, 2020 at 23:14 Unmitigated 89.8k12 gold badges99 silver badges104 bronze badges asked Jun 26, 2020 at 23:12 Moe Moe 731 silver badge7 bronze badges 2- 1 The depth of the search tree is the same as log2 n (the number of elements in the array). – trinalbadger587 Commented Jun 26, 2020 at 23:15
- This might be for cs.stackexchange. – Pogrindis Commented Jun 26, 2020 at 23:15
1 Answer
Reset to default 5Space plexity for the tree itself is proportional to the number of nodes in the tree. Hence, O(N)
Space plexity for your function, validateBst, is the max amount of "stack" memory (function call overhead) allocated to search the entire tree recursively.
The max amount of stack will essentially be the height of the tree from the root node to the leaf node furthest down. In the average case (and best case) - assuming a tree that's fairly well balanced, then the height would be about log₂ N. Hence, space plexity would be O(log₂ N) or simply O(lg N) In a worst case scenario, where the tree is just a sorted linked list branching right with incrementing values, then O(N) as worst case.