Compute Maximum Depth or Height of binary search tree

Given a binary tree, compute its "maxDepth" -- the number of nodes along the longest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0, the maxDepth of the tree below is 3.

      1
   /    \
  2      3
 /   \   /    \
4   5  6   7


Recursive approach

/*
 Compute the "maxDepth" of a tree -- the number of nodes along
 the longest path from the root node down to the farthest leaf node.
*/
int maxDepth(struct node * node) {
    if (node == NULL) {
        return (0);
    } else {
        // compute the depth of each subtree
        int lDepth = maxDepth(node - > left);
        int rDepth = maxDepth(node - > right); // use the larger one
        if (lDepth > rDepth) return (lDepth + 1);
        else return (rDepth + 1);
    }
}

Iterative approach

We could apply the same in-order traversal of a BST in the binary tree. By saying “in-order” traversal I mean traversing the tree such that it reaches the leaf first (deepest). In other words, we are doing a Depth-first Search (DFS). In fact, all three kinds of tree traversal (pre-order, in-order, and post-order) are doing DFS. Therefore, we could modify any existing iterative solution of tree traversals to solve this problem.
As pre-order and in-order iterative traversals are easier to implement, your best bet is to code either one of them during an interview session. As we traverse the tree, we would keep track of the current depth and record each node’s depth, so that we know which depth we are in when we return to the node at a later time. (In pre-order or in-order traversals, it might return several levels above the current level when a node is popped off the stack).
On the other hand, post-order traversal guarantees to return exactly one level above a node that is popped off the stack. Therefore, we could devise a solution utilizing post-order traversal without modifying the existing tree structure. We keep track of the current depth and update the maximum depth as we traverse the tree.
Another solution is to utilize Breadth-first Search (BFS). Unlike DFS, we traverse the tree level by level, thus we are able to obtain the max depth in a direct manner. So BFS is like level order traversal and BFS is not.

Below is the code for finding the maximum depth of a binary tree using post-order traversal, without recursion.

int maxDepthIterative(BinaryTree *root) {
  if (!root) return 0;
  stack<BinaryTree*> s;
  s.push(root);
  int maxDepth = 0;
  BinaryTree *prev = NULL;
  while (!s.empty()) {
    BinaryTree *curr = s.top();
    if (!prev || prev->left == curr || prev->right == curr) {
      if (curr->left)
        s.push(curr->left);
      else if (curr->right)
        s.push(curr->right);
    } else if (curr->left == prev) {
      if (curr->right)
        s.push(curr->right);
    } else {
      s.pop();
    }
    prev = curr;
    if (s.size() > maxDepth)
      maxDepth = s.size();
  }
  return maxDepth;
}

Thanks.