New answers tagged


Heap is an almost complete binary tree. So if you're planning to construct the tree you can just start by filling the values in the tree from top to down and left to right ie, proceed by filling nodes levelwise. Arraylist or linked list doesn't matter here because both stored the level order traversal of the tree. Ex. list.add(0), list.add(1), list.add(1), ...


The space complexity is the amount of space used, which is essentially the size of your call stack in your deepest line of recursion. The runtime is indeed $O(N)$ but the space complexity is $O(H)$ where H is the height of the tree. Even following the link you provided, they state this:


You can simply maintain a (hash)table, just like in the recursive case. Basically, you need to treat items on the stack like function arguments in recursion. Every time you pop items off the stack for processing, you check whether the particular entry in the table had been filled first. This gives you an equivalent memoized algorithm. Additionally, you also ...

Top 50 recent answers are included