Labels

_fuxi (75) _IV (146) _misc (5) {610610 (30) algo (1) automatedTrading (8) banking/economy (3) book (14) c++misc (125) c++real (15) c++STL/java_container (7) cppTemplate (1) db (13) DB_tuning (4) deepUnder (1) dotnet (69) eTip (17) excelVBA (12) finance+sys (34) financeMisc (24) financeRisk (2) financeTechMisc (4) financeVol (21) finmath (17) fixedIncome (25) forex (16) IDE (24) invest (1) java (43) latency (4) LinearAlgebra (3) math (30) matlab (24) memoryMgmt (11) metaPrograming (2) MOM (15) msfm (1) murex (4) nofx (11) nosql (3) OO_Design (1) original_content (4) scriptUnixAutosys (19) SOA (7) socket/stream (15) sticky (1) subquery+join (2) swing (32) sybase (6) tech_orphan (12) tech+fin_career (30) telco (11) thread (21) timeSaver (13) tune (10) US_imm (2) US_misc (2) windoz (20) z_algo+dataStructure (4) z_arch (2) z_c#GUI (30) z_career (10) z_career]US^Asia (2) z_careerBig20 (1) z_careerFinanceTech (11) z_FIX (6) z_forex (31) z_hib (2) z_ikm (7) z_inMemDB (3) z_j2ee (10) z_oq (14) z_php (1) z_py (26) z_quant (4) z_skillist (3) z_spr (5)

Friday, April 10, 2015

bbg algo IV - binary tree inorder walk

Is there a way to design an iterator over a binary search tree with the following properties?
1. Elements are visited in ascending order (i.e. an inorder traversal)
2. next() and hasNext() queries run in O(1) time.
3. Memory usage is O(1)
-------
I feel O(1) memory is impossible since this is recursive (though all recursions can convert to iteration), with a stack data structure of size H := height of tree.

Similarly, hasNext() need to work through the stack of size H, so O(1) run time impossible