Skewed binary tree vs Perfect binary tree - space complexity

Question

Does a skewed binary tree take more space than, say, a perfect binary tree ?

I was solving the question #654 - Maximum Binary Tree on Leetcode, where given an array you gotta make a binary tree such that, the root is the maximum number in the array and the right and left sub-tree are made on the same principle by the sub-array on the right and left of the max number, and there its concluded that in average and best case(perfect binary tree) the space taken would be O(log(n)), and worst case(skewed binary tree) would be O(n).

For example, given nums = [1,3,2,7,4,6,5], the tree would be as such,

      7
    /   \
   3     6
  /  \   / \ 
 1   2  4   5

and if given nums = [7,6,5,4,3,2,1], the tree would be as such,

According to my understanding they both should take O(n) space, since they both have n nodes. So i don't understand how they come to that conclusion. Thanks in advance.

How about showing us how your tree is defined (show some code). And then tell us what you think the answer is, and explain how you arrived at that conclusion. — Jim Mischel

Jim Mischel Jim Mischel · Accepted Answer · 2019-10-17T22:54:58

https://leetcode.com/problems/maximum-binary-tree/solution/

Under "Space complexity," it says:

Space complexity : O(n). The size of the set can grow upto n in the worst case. In the average case, the size will be nlogn for n elements in nums, giving an average case complexity of O(logn).

It's poorly worded, but it is correct. It's talking about the amount of memory required during construction of the tree, not the amount of memory that the tree itself occupies. As you correctly pointed out, the tree itself will occupy O(n) space, regardless if it's balanced or degenerate.

Consider the array [1,2,3,4,5,6,7]. You want the root to be the highest number, and the left to be everything that's to the left of the highest number in the array. Since the array is in ascending order, what happens is that you extract the 7 for the root, and then make a recursive call to construct the left subtree. Then you extract the 6 and make another recursive call to construct that node's left subtree. You continue making recursive calls until you place the 1. In all, you have six nested recursive calls: O(n).

Now look what happens if your initial array is [1,3,2,7,5,6,4]. You first place the 7, then make a recursive call with the subarray [1,3,2]. Then you place the 3 and make a recursive call to place the 1. Your tree is:

             7
         3
       1

At this point, your call depth is 2. You return and place the 2. Then return from the two recursive calls. The tree is now:

             7
         3
       1   2

Constructing the right subtree also requires a call depth of 2. At no point is the call depth more than two. That's O(log n).

It turns out that the call stack depth is the same as the tree's height. The height of a perfect tree is O(log n), and the height of a degenerate tree is O(n).

Skewed binary tree vs Perfect binary tree - space complexity

1 Answers