Time analysis of a Binary Search Tree in-order traversal algorithm

Question

Below is an iterative algorithm to traverse a Binary Search Tree in in-order fashion (first left child , then the parent , finally right child) without using a Stack :

(Idea : the whole idea is to find the left-most child of a tree and find the successor of the node at hand each time and print its value , until there's no more node left.)

void In-Order-Traverse(Node root){
     Min-Tree(root); //finding left-most child
     Node current = root;
  while (current != null){
     print-on-screen(current.key);
     current = Successor(current);
  }
  return;
}

Node Min-Tree(Node root){ // find the leftmost child
   Node current = root;
   while (current.leftChild != null)
      current = current.leftChild;
   return current;
}

Node Successor(Node root){
  if (root.rightChild != null) // if root has a right child ,find the leftmost child of the right sub-tree
    return Min-Tree(root.rightChild);
  else{
    current = root;
    while (current.parent != null && current.parent.leftChild != current)
        current = current.parent;
    return current.parrent;
  }
}

It's been claimed that the time complexity of this algorithm is Theta(n) assuming there are n nodes in the BST , which is for sure correct . However I cannot convince myself as I guess some of the nodes are traversed more than constant number of times which depends on the number of nodes in their sub-trees and summing up all these number of visits wouldn't result time complexity of Theta(n)

Any idea or intuition on how to prove it ?

Answer 1

It is easier to reason with edges rather than nodes. Let us reason based on the code of Successor function.

Case 1 (then branch)

For all nodes with a right child, we will visit the right subtree once ("right-turn" edge), then always visit the left subtree ("left-turn" edges) with Min-Tree function. We can prove that such traversal will create a path whose edges are unique - the edges will not be repeated in any traversal made from any other node with a right child, since the traversal ensures that you never visit any "right-turn" edge of other nodes on the tree. (Proof by construction).

Case 2 (else branch)

For all nodes without a right child (else branch), we will visit the ancestors by following "right-turn" edges until you have to make a "left-turn" edge or encounter the root of the binary tree. Again, the edges in the path generated are unique - will never be repeated in any other traversal made from any other node without a right child. This is because:

• Except for the starting node and the node reached by following "left-turn" edge, all other nodes in between has a right child (which means those are excluded from else branch). The starting node of course does not have a right child.
• Each node has a unique parent (only the root node does not have parent), and the path to parent is either "left-turn" or "right-turn" (the node is a left child or a right child). Given any node (ignoring the right child condition), there is only one path that creates the pattern: many "right-turn" then a "left-turn".
• Since the nodes in between have a right child, there is no way for an edge to appear in 2 traversal starting at different nodes. (Since we are currently considering nodes without a right child).

(The proof here is quite hand-waving, but I think it can be formally proven by contradiction).

Since the edges are unique, the total number of edges traversed in case 1 only (or case 2 only) will be O(n) (since the number of edges in a tree is equal to the number of vertices - 1). Therefore, after summing the 2 cases up, In-Order Traversal will be O(n).

Note that I only know each edge is visited at most once - I don't know whether all edges are visited or not from the proof, but the number of edges is bounded by the number of vertices, which is just right.

We can easily see that it is also Omega(n) (each node is visited once), so we can conclude that it is Theta(n).