I am Harisai

A Binary Search Tree (BST) is a binary tree with the following property:

For every node:

• All nodes in its left subtree have values less than the node’s value.
• All nodes in its right subtree have values greater than the node’s value.

This property holds recursively for all nodes in the tree.

🧩 BST Properties

• In-order traversal of BST → Sorted order
• Minimum node → go leftmost
• Maximum node → go rightmost
• Successor (next greater) → smallest in right subtree
• Predecessor (next smaller) → largest in left subtree

The time complexity of search is O(log n), as in binary search.

🧩 Key Operations

💡 Traversals

Validate Binary Search Tree – LeetCode

A valid BST must satisfy:

For every node:

• All values in the left subtree < current node’s value
• All values in the right subtree > current node’s value

And this condition must hold for all descendants, not just direct children.

⚙️ Core Logic

We use recursion with range limits:

• Each node has a valid range (low, high)
• Node value must satisfy: low < node.val < high
• Recurse left with updated high = node.val
• Recurse right with updated low = node.val

This maintains global correctness across the tree.

🧩 Code Breakdown

var isValidBST = function(root) {
    let flag = true;

    let check = (curr, low, high) => {
        if (!curr) return; // Base case: empty node is valid

        // Node must be within (low, high)
        if (curr.val > low && curr.val < high) {
            // Check left and right with updated bounds
            check(curr.left, low, curr.val);
            check(curr.right, curr.val, high);
        } else {
            flag = false; // Violation found
        }
    }

    check(root, -Infinity, Infinity);
    return flag;
};

⏱️ Complexity

💡 Key Points

• Using low and high ensures cross-subtree validation, not just local comparison.
• Example of invalid case that passes local check but fails global check:

        5
       / \
      1   8
         / \
        4   9
  

  Here, 4 < 5 but appears in right subtree → invalid BST.

• –Infinity and Infinity are used as initial bounds.

🧠 Alternate (In-order Traversal Method)

In-order traversal of a valid BST must produce a strictly increasing sequence.

var isValidBST = function(root) {
    let prev = -Infinity;
    let valid = true;

    function inorder(curr) {
        if (!curr || !valid) return;
        inorder(curr.left);
        if (curr.val <= prev) valid = false;
        prev = curr.val;
        inorder(curr.right);
    }

    inorder(root);
    return valid;
};

✅ Cleaner

✅ Simpler logic (no range tracking)

✅ Still O(n)

💬 Tip for Interviews

If asked:

“Why not just compare node with immediate children?”

👉 Because a violation can occur deeper (not direct child), e.g. right-left node smaller than root.

Hence the range approach is safest.

Search in a Binary Search Tree – LeetCode

A Binary Search Tree (BST) allows efficient search using its property:

Left subtree < Root < Right subtree

We only follow one path at each step instead of scanning all nodes — just like binary search on arrays.

⚙️ Code Logic

var searchBST = function(root, val) {
    if (!root) return root;                 // Reached null → not found
    if (root.val == val) return root;       // Found target node
    if (val < root.val)                     // Search in left subtree
        return searchBST(root.left, val);
    else                                    // Search in right subtree
        return searchBST(root.right, val);
};

🧩 Flow Explanation

1. Start at the root
2. If node value equals target → return node
3. If target < node value → move left
4. If target > node value → move right
5. If null reached → value not found

⏱️ Time & Space

Time: O(h) → h = tree height

Space: O(h) → recursion stack

Balanced BST → h ≈ log₂(n)

Unbalanced BST → h ≈ n

💡 Key Points

• Must return recursive calls so results bubble up
• Returns the node itself (not boolean)
• Useful to access or modify the subtree directly

// top-down approach
var searchBST = function(root, val) {
    if (!root || root.val == val){
     return root
     }
    if (val < root.val){
     return searchBST(root.left, val)
     }
    else {
    return searchBST(root.right, val)
    }
};

//bottom up - generic tree search
var searchBST = function(root, val) {
    if (!root) return null; 
    let left = searchBST(root.left, val);
    let right = searchBST(root.right, val);

    if (root.val === val) return root;
    return left || right;
};

Alternate approach (Iterative)

var searchBST = function(root, val) {
    while (root) {
        if (root.val === val) return root;
        root = val < root.val ? root.left : root.right;
    }
    return null;
};

Iterative avoids recursion stack → same time complexity, better space efficiency.

Insert into a Binary Search Tree – LeetCode

To insert a new value in a BST, find the correct spot where the BST property (left < root < right) remains valid, and attach the new node there.

This uses recursion (top-down) to descend through the tree and returns updated subtrees on the way back up.

⚙️ Code Logic

var insertIntoBST = function(root, val) {
    // Base case → found insertion spot
    if (!root) return new TreeNode(val);
    // Go left if smaller
    if (val < root.val)                    
        root.left = insertIntoBST(root.left, val);
    // Go right if greater
    else                                   
        root.right = insertIntoBST(root.right, val);
    // Return current root to link back
    return root;                           
};

🧩 Flow Explanation

1. If tree is empty → create and return new node
2. Compare val with root.val
   • Smaller → insert into left subtree
   • Greater → insert into right subtree
3. After recursive call, reattach updated subtree to current root
4. Return the root so parent nodes remain connected (return root)

⏱️ Time & Space

Time: O(h) → h = height of tree

Space: O(h) → recursion stack

Balanced tree → O(log n)

Unbalanced tree → O(n)

💡 Key Points

• The return root is critical; it ensures subtree links are updated upward.
• New node is always created at the first null spot found in traversal.
• Insertion order determines tree shape → sorted inserts cause unbalanced BST.
• Works top-down — decision is made at each level before recursive descent.
• this is effectively top-down traversal with bottom-up construction.

Kth Smallest Element in a BST – LeetCode

Finding the K^th smallest element in a Binary Search Tree (BST) leverages the property that in-order traversal of a BST gives sorted order of its elements.

So, the K^th smallest element corresponds to the (K-1)^th index in in-order order.

⚙️ Logic Breakdown

1. Iterative in-order traversal using a stack.
2. Traverse to the leftmost node first (smallest values).
3. Pop from stack → visit node → move to its right.
4. Maintain an array ans to collect values until its length = k.
5. Return ans[k-1] as the result.

🧩 Code Flow

var kthSmallest = function(root, k) {
    let inorder = (root) => {
        let stack = [root]
        let ans = []
        let curr = stack.pop()

        while ((curr || stack.length) && ans.length < k) {
            // go to leftmost
            while (curr) {          
                stack.push(curr)
                curr = curr.left
            }
            // visit node
            curr = stack.pop()       
            ans.push(curr.val)
            // move right
            curr = curr.right        
        }
        return ans
    }

    let ans = inorder(root, k)
    return ans[k - 1]
}

⏱️ Time & Space

• Time: O(H + k)

  (H = tree height, since we stop early after visiting k nodes)

• Space: O(H)

  (stack holds at most height elements)

💡 Alternatives

• Recursive inorder traversal: simpler code but uses call stack.
• Optimized approach: Instead of storing all visited nodes, just keep a counter — stop traversal when counter == k to save space.

🧠 Concept

Same goal — find K^th smallest element in BST, but instead of storing all visited nodes,

we just keep a counter and return early once the K^th node is visited.

This makes it more space-efficient (O(H) stack only, no array).

⚙️ Logic Breakdown

1. Perform in-order traversal (left → node → right).
2. Maintain a global or closure variable count.
3. Decrement k each time a node is visited.
4. When k == 0, that node is the smallest → return it immediately.

🧩 Optimized Code (Iterative)

var kthSmallest = function(root, k) {
    let stack = []
    let curr = root

    while (true) {
        // Move to leftmost node
        while (curr) {
            stack.push(curr)
            curr = curr.left
        }
        curr = stack.pop()
        k--                // one node visited
        if (k === 0) return curr.val
        curr = curr.right  // move right
    }
}

🧠 Alternate Recursive Style (Cleaner but similar logic)

var kthSmallest = function(root, k) {
    let res = null
    const inorder = (node) => {
        if (!node || k === 0) return
        inorder(node.left)
        k--
        if (k === 0) { res = node.val; return }
        inorder(node.right)
    }
    inorder(root)
    return res
}

⏱️ Time & Space

• Time: O(H + k)
• Space: O(H) (stack / recursion depth only)

💡 Insight

This version is ideal when you only need the K^th value, not the full sorted traversal —

it’s both faster (early exit) and lighter on memory.

Lowest Common Ancestor of a Binary Search Tree – LeetCode

The Lowest Common Ancestor (LCA) of two nodes in a tree is the deepest node that has both p and q as descendants.

The approach depends on the type of tree:

• In a BST, node values give direction (ordered structure).
• In a normal binary tree, you must explore both subtrees.

🧩 For Binary Search Tree (BST)

⚙️ Logic

1. BST property: left < root < right.
2. Move down the tree based on p.val and q.val.
   • If both < root → go left
   • If both > root → go right
   • Else → split point found → current node is LCA

📘 Recursive Version

var lowestCommonAncestor = function(root, p, q) {
    if (!root) return null;
    // ensure order
    if (p.val > q.val) [p, q] = [q, p]; 

    if (p.val <= root.val && root.val <= q.val) return root;
    if (q.val < root.val) return lowestCommonAncestor(root.left, p, q);
    return lowestCommonAncestor(root.right, p, q);
};

📘 Iterative Version

var lowestCommonAncestor = function(root, p, q) {
    if (p.val > q.val) [p, q] = [q, p];

    while (root) {
        if (q.val < root.val) root = root.left;
        else if (p.val > root.val) root = root.right;
        else return root;  // split point
    }
    return null;
};

⏱️ Time → O(H)

🧮 Space → O(1) for iterative, O(H) for recursive

💡 Works only in BSTs, where order guides traversal.

🧩 For General Binary Tree

⚙️ Logic

Here, there’s no ordering, so we must explore both subtrees:

1. If current node is null, return null.
2. If current node equals p or q, return it.
3. Recursively find LCA in left and right subtrees.
4. If both sides return non-null → current node is LCA.
5. If only one side returns non-null → propagate it upward.

📘 Code

var lowestCommonAncestor = function(root, p, q) {
    if (!root || root === p || root === q) return root;

    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    // split point
    if (left && right) return root; 
    // propagate non-null 
    return left || right;            
};

⏱️ Time → O(N) (must visit every node)

🧮 Space → O(H) recursion depth

💡 Works for any binary tree, not just BSTs.

💡 Summary