6-line iterative solution in C++


  • 1
    D

    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
    M

    @ducalpha cool


Log in to reply
 

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