6-line iterative solution in C++

  • 1

    An iterative solution is the preferred way as it has O(1) space compared to O(h) space of a recursive solution.
    I assume both nodes p and q are in the tree, so we will always find a non-null LCA.

        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if (p->val > q->val) swap(p, q);
            while (root->val < p->val || root->val > q->val) {
                if (root->val < p->val) root = root->right;
                if (root->val > q->val) root = root->left;
            return root;

  • 0

    @ducalpha cool

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.