Question

An in-order tree walk of an n-node binary search tree can be implemented by finding the minimum element in the tree with TREE-MINIMUM and then making n-1 calls to TREE-SUCCESSOR. Prove that this algorithm runs in Θ(n) time.

Answer 1

public T getMinElement(TreeNode<T> node) {
    //TODO: implement this
    if (node == null){
        return null;
    }
     if (node.getLeftChild() == null){
        return (T) node;
     }
     else{
        return getMinElement(node);
  }
}