CODEWITHSUNDEEP
javascripttime-complexitybig-obinary-search-treespace-complexity
Moe
Moe

Reputation: 73

What is the space complexity of BST?

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 complexity 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?

Upvotes: 3

Views: 8412

Answers (1)

selbie
selbie

Reputation: 104569

Space complexity for the tree itself is proportional to the number of nodes in the tree. Hence, O(N)

Space complexity 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 complexity 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.

Upvotes: 5

Related Questions