Space complexity of validation of a binary search tree

Question

The best algorithm to verify if a binary tree is a BST is given as follows

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
    if(node == null)
        return true;
    if(node.element > MIN 
        && node.element < MAX
        && IsValidBST(node.left,MIN,node.element)
        && IsValidBST(node.right,node.element,MAX))
        return true;
    else 
        return false;
}

The space complexity of this logic is apparently O(logN) which I'm assuming is the cost of recursion. How was the value arrived at?

There is no additional data used other than the method variables and the return value, so indeed, all memory is "cost of recursion". The total cost would hence be linearly proportional to the depth of the tree. In a balanced binary search tree, the depth is O(log n), so indeed, the space complexity would be O(log n) too. However, in general a BST is not necessarily balanced, it could even be a chain of length n, if the root is the minimum, its right child is the second smallest element, and so on. In that case the space complexity of this recursion is O(n). — Vincent van der Weele
– Vincent van der Weele, Commented Feb 4, 2014 at 7:46
How is the question related to c or c++? Does it matter in any way here what language you use? — luk32
– luk32, Commented Feb 4, 2014 at 7:47
Note: it can be done in O(1) if each node has a pointer to its parent, because you can then iterate without maintaining a stack. So it fairly depends on how the binary tree is represented. — Matthieu M.
– Matthieu M., Commented Feb 4, 2014 at 8:25

Vincent van der Weele · Accepted Answer · 2014-02-04 07:48:32Z

12

My comment upgraded to answer:

There is no additional data used other than the method variables and the return value, so indeed, all memory is "cost of recursion". The total cost would hence be linearly proportional to the depth of the tree.

In a balanced binary search tree, the depth is O(log n), so indeed, the space complexity would be O(log n) too. However, in general a BST is not necessarily balanced, it could even be a chain of length n, if the root is the minimum, its right child is the second smallest element, and so on. In that case the space complexity of this recursion is O(n).

answered Feb 4, 2014 at 7:48

Vincent van der Weele

13.2k1 gold badge37 silver badges66 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Aks Over a year ago

but aren't you adding one entry to the recursive stack for each node? isn't that O(n) regardless of how the BST is constructed?

Mats Petersson Over a year ago

The stack is cleaned up when the recursive function reaches a leaf node. So if the tree is balanced, the stack will never be deeper than log n.

Avv Over a year ago

Thank you, but we have elements on both sides of the BST, so why it's O(log n) please?

Vincent van der Weele Over a year ago

@avra, see Mats' comment above yours. Elements are popped from the stack on the way "up", so the size of the stack doesn't exceed the depth of the tree.

Avv Over a year ago

@VincentvanderWeele. Thank you very much! So last question is, why we should have complexity of O(log n) when we do check each left and right subtree at each node? If we have n nodes, then we should have O(nlog n) compelxity for checking validity of BST, please correct if I am wrong? (This is for bruteforce solution not for the above).

|

Collectives™ on Stack Overflow

Space complexity of validation of a binary search tree

1 Answer 1

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related