Lowest Common Ancestor of a BST

🎯

Lowest Common Ancestor of a BST

mediumTREEAmazonFacebookMicrosoft

Imagine you are navigating a family tree of employees in a company organized by hierarchy, and you want to find the closest common manager of two employees quickly.

💡 This problem asks you to find the lowest common ancestor (LCA) of two nodes in a BST. Beginners often struggle because they confuse BST properties with general binary trees and don't leverage the BST ordering to optimize the search.

📋

Problem Statement

Given a binary search tree (BST) and two nodes p and q in the BST, find the lowest common ancestor (LCA) of p and q. The LCA is defined as the lowest node in the BST that has both p and q as descendants (where we allow a node to be a descendant of itself). Input: root of BST, nodes p and q. Output: the LCA node.

The number of nodes in the tree is in the range [1, 10^5]All node values are uniquep and q are different nodes and both exist in the BST

💡

Example

Input"root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8"

Output6

The LCA of nodes 2 and 8 is 6 because 6 is the lowest node that has both 2 and 8 as descendants.

Input"root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4"

Output2

The LCA of nodes 2 and 4 is 2 because a node can be a descendant of itself.

• p is ancestor of q → LCA is p
• q is ancestor of p → LCA is q
• p and q are on different subtrees → LCA is root or intermediate node
• Tree with only one node → LCA is that node

⚠️

Common Mistakes

Not leveraging BST properties and treating tree as general binary tree

Solution becomes inefficient and may time out on large inputs

✅ Use BST ordering to prune search space

Assuming LCA must be strictly ancestor, ignoring that node can be ancestor of itself

Incorrect LCA returned when one node is ancestor of the other

✅ Allow returning p or q if it matches current node during search

Not handling null root or empty tree cases

Code may crash or return incorrect results

✅ Add base case checks for null root

Using recursion without considering stack overflow for deep trees

Stack overflow error on very deep BSTs

✅ Use iterative approach to avoid recursion stack

Comparing node values incorrectly (e.g., using == instead of < or >)

Incorrect traversal direction, wrong LCA found

✅ Use proper comparison operators to decide subtree traversal

🧠

Brute Force (Find Paths and Compare)

💡 This approach exists to build intuition by explicitly finding paths to both nodes and then comparing them. It is straightforward but inefficient, helping beginners understand the problem structure.

Intuition

Find the path from root to p and root to q separately, then compare these paths to find the last common node, which is the LCA.

Algorithm

1. Traverse the BST from root to find the path to node p and store it.
2. Traverse the BST from root to find the path to node q and store it.
3. Compare the two paths node by node until they differ.
4. Return the last common node found in both paths as the LCA.

💡 This algorithm is easy to visualize but requires extra space and repeated traversals, which can be inefficient for large trees.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find_path(root, target, path):
    if not root:
        return False
    path.append(root)
    if root.val == target.val:
        return True
    if (root.left and find_path(root.left, target, path)) or (root.right and find_path(root.right, target, path)):
        return True
    path.pop()
    return False

def lowestCommonAncestor(root, p, q):
    path_p = []
    path_q = []
    find_path(root, p, path_p)
    find_path(root, q, path_q)
    i = 0
    while i < len(path_p) and i < len(path_q) and path_p[i] == path_q[i]:
        i += 1
    return path_p[i-1]

# Example usage:
# Construct BST nodes
# root = TreeNode(6)
# ... build tree ...
# print(lowestCommonAncestor(root, p, q).val)

Line Notes

def find_path(root, target, path):Defines helper to find path from root to target node

if not root:Base case: reached leaf without finding target

path.append(root)Add current node to path as we go down

if root.val == target.val:Check if current node is target

if (root.left and find_path(root.left, target, path)) or (root.right and find_path(root.right, target, path))Recursively search left or right subtree

path.pop()Backtrack if target not found in this path

find_path(root, p, path_p)Find path to node p

find_path(root, q, path_q)Find path to node q

while i < len(path_p) and i < len(path_q) and path_p[i] == path_q[i]:Compare paths to find last common node

return path_p[i-1]Return the last common ancestor node

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
public class Solution {
    public boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null) return false;
        path.add(root);
        if (root.val == target.val) return true;
        if ((root.left != null && findPath(root.left, target, path)) || (root.right != null && findPath(root.right, target, path)))
            return true;
        path.remove(path.size() - 1);
        return false;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = new ArrayList<>();
        List<TreeNode> pathQ = new ArrayList<>();
        findPath(root, p, pathP);
        findPath(root, q, pathQ);
        int i = 0;
        while (i < pathP.size() && i < pathQ.size() && pathP.get(i) == pathQ.get(i)) {
            i++;
        }
        return pathP.get(i - 1);
    }
    // main method and tree construction can be added for testing
}

Line Notes

public boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path)Helper to find path from root to target

if (root == null) return false;Base case: no node found

path.add(root);Add current node to path

if (root.val == target.val) return true;Check if current node is target

if ((root.left != null && findPath(root.left, target, path)) || (root.right != null && findPath(root.right, target, path)))Search left or right subtree recursively

path.remove(path.size() - 1);Backtrack if target not found

findPath(root, p, pathP);Find path to p

findPath(root, q, pathQ);Find path to q

while (i < pathP.size() && i < pathQ.size() && pathP.get(i) == pathQ.get(i))Compare paths to find last common node

return pathP.get(i - 1);Return LCA node

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool findPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path) {
    if (!root) return false;
    path.push_back(root);
    if (root->val == target->val) return true;
    if ((root->left && findPath(root->left, target, path)) || (root->right && findPath(root->right, target, path)))
        return true;
    path.pop_back();
    return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    vector<TreeNode*> pathP, pathQ;
    findPath(root, p, pathP);
    findPath(root, q, pathQ);
    int i = 0;
    while (i < pathP.size() && i < pathQ.size() && pathP[i] == pathQ[i])
        i++;
    return pathP[i - 1];
}
// main function and tree construction can be added for testing

Line Notes

bool findPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path)Helper to find path from root to target node

if (!root) return false;Base case: reached null node

path.push_back(root);Add current node to path

if (root->val == target->val) return true;Check if current node is target

if ((root->left && findPath(root->left, target, path)) || (root->right && findPath(root->right, target, path)))Recursively search left or right subtree

path.pop_back();Backtrack if target not found

findPath(root, p, pathP);Find path to p

findPath(root, q, pathQ);Find path to q

while (i < pathP.size() && i < pathQ.size() && pathP[i] == pathQ[i])Compare paths to find last common node

return pathP[i - 1];Return LCA node

function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}
function findPath(root, target, path) {
    if (!root) return false;
    path.push(root);
    if (root.val === target.val) return true;
    if ((root.left && findPath(root.left, target, path)) || (root.right && findPath(root.right, target, path)))
        return true;
    path.pop();
    return false;
}
function lowestCommonAncestor(root, p, q) {
    const pathP = [];
    const pathQ = [];
    findPath(root, p, pathP);
    findPath(root, q, pathQ);
    let i = 0;
    while (i < pathP.length && i < pathQ.length && pathP[i] === pathQ[i]) {
        i++;
    }
    return pathP[i - 1];
}
// Example usage:
// let root = new TreeNode(6);
// ... build tree ...
// console.log(lowestCommonAncestor(root, p, q).val);

Line Notes

function findPath(root, target, path)Helper to find path from root to target

if (!root) return false;Base case: no node found

path.push(root);Add current node to path

if (root.val === target.val) return true;Check if current node is target

if ((root.left && findPath(root.left, target, path)) || (root.right && findPath(root.right, target, path)))Recursively search left or right subtree

path.pop();Backtrack if target not found

findPath(root, p, pathP);Find path to p

findPath(root, q, pathQ);Find path to q

while (i < pathP.length && i < pathQ.length && pathP[i] === pathQ[i])Compare paths to find last common node

return pathP[i - 1];Return LCA node

⏱

Complexity

TimeO(n) in worst case, where n is number of nodes, because we may traverse the tree twice to find paths

SpaceO(n) for storing paths and recursion stack

Finding each path can take O(n) time in worst case, and storing paths requires O(n) space. Comparing paths is O(n) as well.

💡 For n=20 nodes, this means up to 40 node visits plus storing paths, which is inefficient for large trees.

Interview Verdict: Accepted but inefficient; useful for understanding

This approach is easy to implement but not optimal. It helps beginners understand the problem before moving to better solutions.

🧠

Better (Recursive BST Property Exploitation)

💡 This approach leverages BST properties to avoid searching entire paths, improving efficiency by pruning unnecessary branches.

Intuition

Because BST nodes are ordered, if both p and q are smaller than current node, LCA lies in left subtree; if both are greater, LCA lies in right subtree; otherwise current node is LCA.

Algorithm

1. Start at root node.
2. If both p and q values are less than root's value, recurse into left subtree.
3. If both p and q values are greater than root's value, recurse into right subtree.
4. Otherwise, root is the LCA.

💡 This algorithm is more efficient because it uses BST ordering to avoid unnecessary subtree searches.

Recurrence:LCA(root) = if p.val < root.val and q.val < root.val then LCA(root.left) else if p.val > root.val and q.val > root.val then LCA(root.right) else root

</>

Code

def lowestCommonAncestor(root, p, q):
    if root is None:
        return None
    if p.val < root.val and q.val < root.val:
        return lowestCommonAncestor(root.left, p, q)
    elif p.val > root.val and q.val > root.val:
        return lowestCommonAncestor(root.right, p, q)
    else:
        return root

# Example usage:
# print(lowestCommonAncestor(root, p, q).val)

Line Notes

if root is None:Base case: empty subtree

if p.val < root.val and q.val < root.val:Both nodes smaller, go left

return lowestCommonAncestor(root.left, p, q)Recurse left subtree

elif p.val > root.val and q.val > root.val:Both nodes greater, go right

return lowestCommonAncestor(root.right, p, q)Recurse right subtree

else:Nodes split, current root is LCA

return rootReturn LCA node

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    } else {
        return root;
    }
}
// main method and tree construction can be added for testing

Line Notes

if (root == null) return null;Base case: empty subtree

if (p.val < root.val && q.val < root.val)Both nodes smaller, go left

return lowestCommonAncestor(root.left, p, q);Recurse left subtree

else if (p.val > root.val && q.val > root.val)Both nodes greater, go right

return lowestCommonAncestor(root.right, p, q);Recurse right subtree

elseNodes split, current root is LCA

return root;Return LCA node

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return nullptr;
    if (p->val < root->val && q->val < root->val) {
        return lowestCommonAncestor(root->left, p, q);
    } else if (p->val > root->val && q->val > root->val) {
        return lowestCommonAncestor(root->right, p, q);
    } else {
        return root;
    }
}
// main function and tree construction can be added for testing

Line Notes

if (!root) return nullptr;Base case: empty subtree

if (p->val < root->val && q->val < root->val)Both nodes smaller, go left

return lowestCommonAncestor(root->left, p, q);Recurse left subtree

else if (p->val > root->val && q->val > root->val)Both nodes greater, go right

return lowestCommonAncestor(root->right, p, q);Recurse right subtree

elseNodes split, current root is LCA

return root;Return LCA node

function lowestCommonAncestor(root, p, q) {
    if (!root) return null;
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    } else {
        return root;
    }
}
// Example usage:
// console.log(lowestCommonAncestor(root, p, q).val);

Line Notes

if (!root) return null;Base case: empty subtree

if (p.val < root.val && q.val < root.val)Both nodes smaller, go left

return lowestCommonAncestor(root.left, p, q);Recurse left subtree

else if (p.val > root.val && q.val > root.val)Both nodes greater, go right

return lowestCommonAncestor(root.right, p, q);Recurse right subtree

elseNodes split, current root is LCA

return root;Return LCA node

⏱

Complexity

TimeO(h), where h is the height of the BST

SpaceO(h) due to recursion stack

Each recursive call moves down one level of the tree, so time and space depend on tree height, which is O(log n) for balanced BSTs and O(n) worst case.

💡 For a balanced BST with 20 nodes, this means about 5 steps, much faster than brute force.

Interview Verdict: Accepted and efficient for balanced BSTs

This approach is optimal for BSTs and is the standard solution interviewers expect.

🧠

Optimal (Iterative BST Property Exploitation)

💡 This approach optimizes the recursive solution by using iteration to avoid recursion overhead and stack usage.

Intuition

Use a loop to traverse the BST from root, moving left or right based on p and q values until the split point (LCA) is found.

Algorithm

1. Initialize current node as root.
2. While current node is not null:
3. If both p and q values are less than current node's value, move to left child.
4. Else if both p and q values are greater than current node's value, move to right child.
5. Else current node is LCA; break and return it.

💡 This iterative approach is straightforward and efficient, avoiding recursion stack overhead.

</>

Code

def lowestCommonAncestor(root, p, q):
    current = root
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

# Example usage:
# print(lowestCommonAncestor(root, p, q).val)

Line Notes

current = rootStart traversal from root

while current:Loop until LCA found or tree ends

if p.val < current.val and q.val < current.val:Both nodes smaller, go left

current = current.leftMove to left child

elif p.val > current.val and q.val > current.val:Both nodes greater, go right

current = current.rightMove to right child

else:Nodes split, current is LCA

return currentReturn LCA node

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode current = root;
    while (current != null) {
        if (p.val < current.val && q.val < current.val) {
            current = current.left;
        } else if (p.val > current.val && q.val > current.val) {
            current = current.right;
        } else {
            return current;
        }
    }
    return null;
}
// main method and tree construction can be added for testing

Line Notes

TreeNode current = root;Initialize traversal pointer

while (current != null)Loop until LCA found or end

if (p.val < current.val && q.val < current.val)Both nodes smaller, go left

current = current.left;Move left

else if (p.val > current.val && q.val > current.val)Both nodes greater, go right

current = current.right;Move right

elseNodes split, current is LCA

return current;Return LCA node

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* current = root;
    while (current) {
        if (p->val < current->val && q->val < current->val) {
            current = current->left;
        } else if (p->val > current->val && q->val > current->val) {
            current = current->right;
        } else {
            return current;
        }
    }
    return nullptr;
}
// main function and tree construction can be added for testing

Line Notes

TreeNode* current = root;Initialize traversal pointer

while (current)Loop until LCA found or end

if (p->val < current->val && q->val < current->val)Both nodes smaller, go left

current = current->left;Move left

else if (p->val > current->val && q->val > current->val)Both nodes greater, go right

current = current->right;Move right

elseNodes split, current is LCA

return current;Return LCA node

function lowestCommonAncestor(root, p, q) {
    let current = root;
    while (current) {
        if (p.val < current.val && q.val < current.val) {
            current = current.left;
        } else if (p.val > current.val && q.val > current.val) {
            current = current.right;
        } else {
            return current;
        }
    }
    return null;
}
// Example usage:
// console.log(lowestCommonAncestor(root, p, q).val);

Line Notes

let current = root;Initialize traversal pointer

while (current)Loop until LCA found or end

if (p.val < current.val && q.val < current.val)Both nodes smaller, go left

current = current.left;Move left

else if (p.val > current.val && q.val > current.val)Both nodes greater, go right

current = current.right;Move right

elseNodes split, current is LCA

return current;Return LCA node

⏱

Complexity

TimeO(h), where h is the height of the BST

SpaceO(1) additional space

Iterative traversal visits nodes down the tree height only, no recursion stack used.

💡 For balanced BST with 20 nodes, this means about 5 steps and constant extra space.

Interview Verdict: Accepted and optimal for interviews

This is the best approach to code in interviews for this problem due to its efficiency and simplicity.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the iterative BST property approach is best for efficiency and clarity. Brute force is good for initial explanation but not for coding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Find Paths and Compare)	O(n)	O(n)	Yes (due to recursion in path finding)	Yes (paths explicitly stored)	Mention only - never code
2. Recursive BST Property Exploitation	O(h)	O(h)	Yes (deep recursion possible)	N/A	Good to explain and code if comfortable with recursion
3. Iterative BST Property Exploitation	O(h)	O(1)	No	N/A	Best approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then move to optimized BST property solutions. Practice coding and explaining each step clearly.

How to Present

Step 1: Clarify the problem and confirm BST properties and input guarantees.Step 2: Describe the brute force approach of finding paths and comparing them.Step 3: Explain how BST ordering allows pruning and leads to a recursive solution.Step 4: Present the iterative solution as the optimal approach.Step 5: Code the iterative solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests your understanding of BST properties, ability to optimize from brute force, and clean coding skills. They also check if you handle edge cases and explain your approach clearly.

Common Follow-ups

• What if the tree is not a BST? → Use general binary tree LCA algorithm.
• Can you find LCA without parent pointers? → Yes, using recursion or iteration as shown.

💡 These follow-ups test your adaptability and understanding of related problems.

🔍

Pattern Recognition

When to Use

1) Input is a BST, 2) Need to find common ancestor of two nodes, 3) Nodes guaranteed to exist, 4) Want efficient search using BST ordering

Signature Phrases

'lowest common ancestor''binary search tree''both nodes are descendants''node can be descendant of itself'

NOT This Pattern When

General binary tree LCA problems without BST ordering

Similar Problems

Lowest Common Ancestor of a Binary Tree - similar but no BST propertyValidate Binary Search Tree - uses BST ordering logicFind Distance Between Nodes in BST - uses LCA to compute distance

Practice

1. You are given a binary search tree and a value range [low, high]. You need to remove all nodes whose values fall outside this range, ensuring the resulting tree remains a valid BST. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Iteratively prune the BST by adjusting pointers using BST properties without rebuilding the tree.

B. Apply dynamic programming to store subtrees and decide which to keep based on range constraints.

C. Use a greedy approach to remove nodes one by one by checking each node's value and deleting if out of range.

D. Perform an inorder traversal to collect all valid nodes, then rebuild the BST from the sorted list.

Solution

1. Step 1: Understand the problem constraints

   The problem requires trimming nodes outside [low, high] while preserving BST properties efficiently.

2. Step 2: Evaluate approaches

   Rebuilding the tree (A) wastes time and space. Greedy removal (C) is inefficient and may break BST structure. DP (B) is unnecessary and overcomplicates. Iterative pruning (D) leverages BST properties to skip subtrees and adjust pointers in O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Iterative pruning uses BST properties optimally [OK]

Hint: Use BST properties to prune iteratively for optimal trimming [OK]

Common Mistakes:

• Rebuilding tree wastes space and time
• Greedy removal breaks BST structure

2. What is the space complexity of the optimal Morris inorder traversal approach used to recover a BST with two swapped nodes, and why might some candidates mistakenly believe it is higher?

medium

A. O(1) because Morris traversal modifies tree pointers temporarily without extra data structures

B. O(n) due to storing node values during traversal

C. O(h) where h is tree height due to recursion stack in inorder traversal

D. O(log n) because of balanced tree height and implicit stack usage

Solution

1. Step 1: Understand Morris traversal space usage

   Morris traversal uses threaded binary tree pointers to traverse without recursion or stack, so no extra space beyond a few pointers.

2. Step 2: Identify common misconception

   Candidates often confuse it with recursive or stack-based inorder traversal, which uses O(h) space, or with storing values in a list, which uses O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Morris traversal achieves O(1) space by temporarily modifying tree pointers [OK]

Hint: Morris traversal uses threaded pointers, no stack needed [OK]

Common Mistakes:

• Assuming recursion stack space applies
• Confusing storing values with traversal space
• Believing temporary pointer changes increase space

3. Consider the following buggy code for trimming a BST. Which line contains the subtle bug that can cause the resulting tree to violate BST properties or cause runtime errors?

medium

A. Line 3: root = root.left when root.val < low

B. Line 5: root = root.left when root.val > high

C. Line 10: cur.left = cur.left.right inside left subtree trimming

D. Line 16: cur.right = cur.right.left inside right subtree trimming

Solution

1. Step 1: Check root adjustment logic

   If root.val < low, root should move to root.right, not root.left, to find valid nodes.

2. Step 2: Verify other lines

   Line 5 correctly moves root to root.left if root.val > high. Lines 10 and 16 correctly adjust subtree pointers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect pointer move causes invalid pruning or infinite loop [OK]

Hint: Root moves wrong direction when value < low [OK]

Common Mistakes:

• Confusing left and right subtree moves
• Incorrect pointer updates causing invalid BST

4. What is the time complexity of the optimal solution that uses inorder traversal followed by the two-pointer technique to solve the Two Sum IV in BST problem, assuming the BST has n nodes?

medium

A. O(n log n) due to sorting the inorder traversal array

B. O(n^2) because two-pointer approach checks all pairs in worst case

C. O(n) because inorder traversal and two-pointer scan each take linear time

D. O(log n) because BST properties reduce search space

Solution

1. Step 1: Analyze inorder traversal time

   Inorder traversal visits each node once, O(n) time.

2. Step 2: Analyze two-pointer scan time

   Two pointers move inward at most n steps total, O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both steps are linear, total O(n) time [OK]

Hint: Inorder + two-pointer each O(n), total O(n) [OK]

Common Mistakes:

• Assuming sorting is needed after inorder traversal
• Confusing two-pointer with nested loops
• Thinking BST reduces complexity to log n

5. The following code attempts to validate a BST using inorder traversal. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line checking if node is null (if not node: return true)

B. Line updating prev[0] = node.val

C. Line comparing node.val < prev[0] instead of node.val <= prev[0]

D. Line calling inorder(node.left)

Solution

1. Step 1: Identify BST strict inequality

   BST requires node.val to be strictly greater than previous inorder value; using < instead of <= allows duplicates.

2. Step 2: Understand impact of bug

   Using node.val < prev[0] misses the case when node.val == prev[0], incorrectly allowing duplicates and invalid BSTs.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Strict inequality check is essential to reject duplicates [OK]

Hint: BST nodes must be strictly increasing in inorder traversal [OK]

Common Mistakes:

• Allowing duplicates by using < instead of <=
• Not resetting prev between calls
• Only comparing immediate children