CODEWITHSUNDEEP
algorithmbig-obinary-search-treetime-complexity
Amit
Amit

Reputation: 817

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

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;

}
}

Upvotes: 0

Views: 3215

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55609

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.

Upvotes: 1

Related Questions