How to Rebuild a binary tree from Inorder and Preorder traversals ?

This is a well known problem where given any two traversals of a tree such as inorder & preorder or inorder & postorder or inorder & levelorder traversals we need to rebuild the tree. The following procedure demonstrates on how to rebuild tree from given inorder and preorder traversals of a binary tree: Preorder traversal visits...

Continue

O(1) stack operations.

Design a datastructure to implement a stack such that ALL of push(), pop() and getMax() functions work in O(1) time. You have infinite memory at your disposal. Also note that function getMax() just returns the element with maximum value in the stack and NOT delete it from the stack like what pop() does. Insight : compress the information using diffPUSH :if stack emptypush(elem)push(elem)elsemin = pop()push(elem-min)push(min)POP :min =...

Continue