Finding left most node in a binary tree

Question

I need to find the left most node in a binary tree. It may sound naive but it isnt. I tried this but i think it will fail :

Node* findLeftMostNode(Node* root){
    if(root->left==null)
       return root;
    findLeftMostNode(root->left);
}

The problem is that the left mode node can be at any level so we need to handle that.

          X
          \
           X
           /\
          X  X
         /
        X
       /
      X

Answer 1

With this way of calculating the “leftness” of a node, you always have to recurse to both child nodes, because any child could contain a sequence of n nodes going left for any n.

So, the solution is actually quite simple: calculate the x for each node in the tree and return the smallest one:

Node* findLeftmostNode(Node* current, int x = 0)
{
    current->x = x;

    Node* best;
    // leftmost child in the left subtree is always better than the root
    if (current->left == null)
        best = current;
    else
        best = findLeftmostNode(current->left, x - 1);

    if (current->right != null)
    {
        Node* found = findLeftmostNode(current->right, x + 1);
        if (found->x < best->x)
            best = found;
    }

    return best;
}