title: Balanced BST vs Balanced Binary Tree: Complexity
body: <p>I am determining the complexity of different operations on a balanced BST vs a balanced BT. I want to know if I have figured out the right complexities. The operations are as follows,</p>
  
  <p>Finding the Smallest Element</p>
  
  <p>This would be O(LogN)for a balanced BST and O(N) for a BT. </p>
  
  <p>Creating a List of Elements in PreOrder</p>
  
  <p>This would be O(N) for both since all nodes will be traversed.</p>
  
  <p>Creating a List of Elements Smaller than Some Value v</p>
  
  <p>This would be O(N) for both although implementation wise a balanced BST could be much faster using in-order traversal.</p>
  
  <p>Removing all leaves from a tree</p>
  
  <p>This would be O(N) for both, all nodes need to be traversed to find leaf nodes.</p>
  
  <p>Are these conclusions correct?</p>