How do i calculate space complexity for checking if binary search tree is balanced?

Question

I want to check if binary search tree provided to me is balanced or not.

Since tree already exists in memory, there is no additional storage needed while checking if tree is balanced when traversing through nodes.

So I assume space complexity would be O(1).

Is it correct?

// Definition for binary tree
  class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
    val = x;
}
 }

  public class Solution {
public boolean isBalanced(TreeNode root) {
    if (root == null)
        return true;

    if (getHeight(root) == -1)
        return false;

    return true;
}

public int getHeight(TreeNode root) {
    if (root == null)
        return 0;

    int left = getHeight(root.left);
    int right = getHeight(root.right);

    if (left == -1 || right == -1)
        return -1;

    if (Math.abs(left - right) > 1) {
        return -1;
    }

    return Math.max(left, right) + 1;

}
}

Do tree nodes have parent pointers? Because that makes a big difference — Mooing Duck
– Mooing Duck, Commented May 30, 2014 at 21:39
Well no, actually each node will have reference to child nodes only. How would that make difference? — Amit
– Amit, Commented May 30, 2014 at 21:40
Did you actually try to derive an algorithm? Do you even have a definition of balance for BSTs? — Fred Foo
– Fred Foo, Commented May 30, 2014 at 21:41
Create an algorithm before you start making assumptions about space complexity. — Bernhard Barker
– Bernhard Barker, Commented May 30, 2014 at 21:55
@MooingDuck is right, except I would say that stack space must be included in the complexity. Here that would mean that any kind of recursion (e.g. depth-first) will be at least O(d), if d is the height of the tree. — j_random_hacker
– j_random_hacker, Commented May 30, 2014 at 22:01

Bernhard Barker · Accepted Answer · 2014-05-30 22:27:31Z

Your algorithm is O(height) space, not O(1) - you need to store 1 recursive function call in memory for every node as you recurse down the tree, and you can never go deeper than O(height) in the tree (before you return and can get rid of the already-fully-processed nodes).

For a tree like:

_{(Image reference - Wikipedia)}

Your calls will go like this:

getHeight(8)
  getHeight(3)
    getHeight(1)
    getHeight(6)
      getHeight(4)
      getHeight(7)
  getHeight(10)
    getHeight(14)
    getHeight(13)

Here, getHeight(8) calls getHeight(3), which calls getHeight(1) and getHeight(6), etc.

After we've finished calling the function for 1 (returning the result to the call for 3), we don't need to keep that in memory any more, thus the maximum number of calls that we keep in memory is equal to the height of the tree.

It can be done in O(1) space, but it's fairly complicated and really slow (much slower than the O(n) that your solution takes).

The key is that we have a binary search tree, so, given a node, we'd know whether that node is in the left or right subtree of any ancestor node, which we can use to determine the parent of a node.

I may create a separate Q&A going into a bit more details at some point.

Collectives™ on Stack Overflow

How do i calculate space complexity for checking if binary search tree is balanced?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related