🗓 Daily LeetCode Progress – Day 22

Problems Solved:

#230 Kth Smallest Element in a BST
#236 Lowest Common Ancestor of a Binary Tree

This continues my daily series (Day 22: Inorder Traversal + Divide & Conquer). Today I solved two core binary-tree patterns: using an inorder traversal on a BST to extract sorted order and find the k‑th smallest, and a clean divide‑and‑conquer DFS to compute the LCA in a general binary tree.

💡 What I Learned

Kth Smallest in BST (#230): Because an inorder traversal of a BST yields values in non‑decreasing order, we can increment a counter during traversal and return when the counter hits k. This creates a simple early‑exit pattern.
LCA in Binary Tree (#236): A post‑order style DFS works neatly: if a subtree returns non‑null for both p and q, the current node is the LCA. If only one side is non‑null, bubble that node upward.
General tips:
- Don’t compare node.val to p/q objects—compare nodes directly for LCA.
- For BST inorder solutions, keep a mutable counter/state ( member variables in C++ or self fields in Python) and stop early whenfound.

🧩 #230 — Kth Smallest Element in a BST

C++ (Recursive Inorder with early stop, O(n))

/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *   int val;
  *   TreeNode *left;
  *   TreeNode *right;
  *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
  *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  * };
 */
class Solution {
public:
    int count = 0;
    int result = -1;

    void inorder(TreeNode* node, int k) {
        if (!node || result != -1) return;
        inorder(node->left, k);
        count++;
        if (count == k) {
            result = node->val;
            return;
        }
        inorder(node->right, k);
    }

    int kthSmallest(TreeNode* root, int k) {
        inorder(root, k);
        return result;
    }
};

Python (Recursive Inorder, O(n))

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def kthSmallest(self, root, k):
        self.count = 0
        self.result = None

        def inorder(node):
            if not node:
                return
            inorder(node.left)
            self.count += 1
            if self.count == k:
                self.result = node.val
                return
            inorder(node.right)

        inorder(root)
        return self.result

Key idea: Inorder on BST == sorted order. Maintain a counter and return once k is reached.

Complexity: O(h + k) average when the early stop prunes (worst‑case O(n)), O(h) recursion stack where h is tree height.

🧩 #236 — Lowest Common Ancestor of a Binary Tree

C++ (Divide & Conquer DFS, O(n))

/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *   int val;
  *   TreeNode *left;
  *   TreeNode *right;
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if (left && right) return root;   // p and q in different subtrees
        return left ? left : right;       // both in the same subtree or not found here
    }
};

Python (Divide & Conquer DFS, O(n))

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root
        return left if left else right

Key idea: Post‑order style recursion: return a non‑null pointer if p or q is found in a subtree; if both sides return non‑null, the current node is the LCA.

Complexity: O(n) time (each node visited once), O(h) recursion stack.

📸 Achievements

Implemented inorder traversal with early stopping to fetch the k‑th smallest efficiently on BSTs.
Solved LCA on general binary trees with a concise divide‑and‑conquer DFS.

📦 Complexity Recap

Kth Smallest (BST): O(h + k) average (worst O(n)), O(h) stack.

LCA (Binary Tree): O(n) time, O(h) stack.

📣 Join the Journey

I’m solving and documenting problems daily in both Python and C++, covering trees, graphs, stacks/queues, and classic traversal patterns. Follow along if you’re into clean patterns and cross‑language implementations!

Links: