all of its tree levels have as many nodes as there can be. So, the minimum possible value of N is 1, regardless of the value of K.Ī tree of specific height has maximum number of leaf nodes when it is full, i.e. This is the case that the tree is in the shape of a linked list - all of its nodes but the single leaf have exactly one child. This question tests your understanding of trees in general, and the binary search tree structure in relation to its use.Ī binary tree (or any tree for this case) of height K can have as few as K+1 nodes with only one of them a leaf. The time taken is not dependent on the size of the input. `peek()` returns the top element like `pop()` does, but without removing it: return stack Įach of these operations have the complexity O(1), which is the complexity of core stack data structure. It is the logical inverse of `push()`: return stack `pop()` operation removes and returns the element at the top of the stack. The `stackTop` value is incremented after that: stack=entry `push(entry)` operation, it is placed at the cell that `stackTop` currently shows. When a new entry is made to the stack, i.e. The boilerplate code to cover the edge cases that the stack is full or empty are omitted. The following code shows the overall logic of the 3 main stack operations. So by this, all array cells with indexes less than stackTop hold entries in them, and all those with greater indexes are empty. the index that is 1 greater than the index of last element inserted to the stack. In such an implementation, a pointer variable, say `stackTop`, should be maintained always to point to the next available cell, i.e. entries inserted after itself.Īn array can be used by adding elements to its consecutive cells starting from its first cell at index 0. An entry can not be reached as long as there are entries on top of it, i.e. All element operations are on one end of the stack, called the stack top. Stack is a Last-In-First-Out (LIFO) data structure. This question tests your understanding of both an array and stack data structures.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |