On Tue, Sep 20, 2016, at 22:34, Steve D'Aprano wrote: > I'm afraid I don't understand this. This is a standard binary tree > inorder traversal. Each node is visited once, and there are N nodes, > so I make that out to be O(N) not O(N log N). I'm afraid I can't parse > your final clause: > > "since values from the leaves of the tree have to be yielded > multiple times to the top of the tree" > > Each leaf is yielded once, and I don't understand what you mean by > yielding to the top of the tree.
His point is that in order for the top-level iterator to return a given node there's a yield call in the top level's iterator , that calls the next level's iterator's yield, that calls the next one, so on, in a call stack log(n) levels deep. -- https://mail.python.org/mailman/listinfo/python-list
