While both keys fall on the same side of the current node, you are still above both of them, so you have not gone too far. The first node where they fall on opposite sides, or where one of them equals the node, is the last node shared by both root-to-node paths, which is the definition of the lowest common ancestor. The order of the two arguments does not matter, because each test checks both keys against the current node. The loop does assume both keys are in the tree: give it two absent values and it returns the point where they would have split, or walks off the bottom and trips whichever non-null assertion it reaches, c.left going down the left edge or c.right going down the right one.