Validate a BST and find the inorder successor

Why it matters

"Validate a BST" is one of the most failed interview questions. The first idea most people try is wrong, and the mistake is subtle. The successor question uses the same ideas, and it appears in interviews, in database code and in the standard containers. This lesson teaches you to see the trap, to write the correct checks, and to explain why they are correct.

You will also see why small details matter. A bound set to the wrong sentinel value makes a correct tree look invalid. A comparison that uses < where <= is needed accepts a tree that should be rejected. Each of these errors is short to fix once you can see it.

The tempting check that is wrong

Suppose someone hands you a tree and asks whether it is a BST. The first idea is to check each node against its direct children. The left child must be smaller, and the right child must be larger. If every node passes, the tree must be fine.

That idea is wrong. Here is a tree that passes every direct check:

      5
     / \
    1   6
       / \
      3   7

Look at each node. The node 5 has children 1 and 6. One is smaller and six is larger, so it passes. The node 1 has no children, so it passes. The node 6 has children 3 and 7. Three is smaller than 6, and seven is larger, so it passes. The node 3 and the node 7 are leaves, so they pass. Every direct check succeeds.

Yet the tree is not a BST. The value 3 sits in the right subtree of 5, and the rule says every value in the right subtree of 5 must be larger than 5. Three is not larger than 5, so the rule is broken.

Each parent passes its check, but the value 3 sits in the right subtree of 5

The lesson is that a node must be checked against every ancestor above it, not only against its parent. The value 3 is below 6 and also below 5. The check must remember the limits set by all the ancestors.

Validate with ranges

Here is the correct idea. Every node must lie inside an allowed range. The root can hold any value, so its range is unlimited. When you go left from a node with value v, every value below must be smaller than v. So the range for the left child is the same lower bound, with v as the new upper bound. When you go right, the range for the right child keeps the upper bound and uses v as the new lower bound.

You can see the walk as shrinking a window. The window starts wide open. Each step narrows it. A node that falls outside its window breaks the rule.

Let us apply it to the tree above. The root 5 gets the window (negative infinity, positive infinity). Node 1 is on the left, so its window is (negative infinity, 5). The value 1 fits. Node 6 is on the right, so its window is (5, positive infinity). The value 6 fits. Node 3 is the left child of 6, so its window is (5, 6). The value 3 is not inside (5, 6), so the check fails right there.

Here is the code. It uses long long for the bounds, which we explain in a moment.

The output is:

bad: invalid
good: valid
extreme: valid

Look at the valid function. The base case if (!n) return true; says an empty tree is valid. The check n->val <= lo || n->val >= hi makes the window strict, so a value equal to a bound is rejected. This matches the rule that there are no duplicates. The two recursive calls pass down the narrowed window. The function returns true only if both sides are valid.

Why the bounds are long long

The window needs a starting value that no node can break. The natural choice is the smallest and largest values an int can hold, which are INT_MIN and INT_MAX. But those values are real values that a tree may contain. The root extreme holds INT_MIN. If you start with the window (INT_MIN, INT_MAX), the root fails the test n->val <= lo, because INT_MIN is not strictly greater than INT_MIN. So a valid tree is rejected.

Using long long avoids the problem. The long long range is wider than the int range, so the sentinels LLONG_MIN and LLONG_MAX are smaller and larger than every int value. The comparison n->val <= lo works with an int on the left and a long long on the right, because C++ converts the int to long long.

Here is what the broken version prints. It is the same valid function, but with int bounds that also print each step, so you can see the window.

visit -2147483648 range (-2147483648, 2147483647)
invalid

The window (-2147483648, 2147483647) starts with the root value at its lower end. The first check fails, and the program reports invalid for a tree that is valid. The printed range is the clue. When a valid tree is rejected at its root, look at the bounds first.

The cost of validation is O(n), because each node is visited once. The extra memory is O(h) for the recursion.

Validate with an inorder walk

There is a second method that uses something you already know. In a valid BST, the inorder walk prints values in strictly increasing order. So you can walk the tree in order and check that each value is larger than the one before it. If any value is not larger, the tree is invalid.

The walk needs to remember the last value it visited. The cleanest way is to pass a reference to one variable that holds that value. Each visit compares the node with the stored value and then updates it. Here is the program. It reads a tree from the Input box in a simple form.

The input is the root, then one pair of children for each node in the order you meet the nodes. A pair holds the left child and the right child. The word x means there is no child. The first pair belongs to the root, the next pair belongs to the first child listed, and so on. This is the order in which a queue would hand out the nodes, so the program uses a queue.

For the tree 5 with left 1 and right 6, where 6 has children 3 and 7, the input is:

5 1 6 x x 3 7 x x x x

Read it as follows. The root is 5. The pair for 5 is 1 6. The pair for 1 is x x, because 1 has no children. The pair for 6 is 3 7. The pairs for 3 and 7 are both x x. Five pairs, one per node, and that is all the input.

Type this into the Input box:

5 1 6 x x 3 7 x x x x

The output is:

invalid

Now type this instead, which is the tree 5 with left child 3 (children 1 and 4) and right child 8:

5 3 8 1 4 x x x x x x

The output is:

valid

Trace the first run. The inorder walk visits 1, then 5, then 3, then 6, then 7. Its values are 1, 5, 3, 6, 7. When the walk reaches 3, the last value seen is 5, and 3 is not larger, so the function returns false. The check fails at that point, and the program prints invalid.

Now the prev variable has type long long, and it starts at LLONG_MIN. That is the same reason as before. If you started it at INT_MIN, a tree whose smallest value is INT_MIN would fail on its first node, because n->val <= prev would be true.

The inorder method is O(n) in time and O(h) in stack memory. Its advantage is that it does not need bounds at all. Its disadvantage is that you must remember the previous value, which is a little more state to manage.

Step through an inorder walk below. This is the same walk the validator uses. Watch the values come out in order, and check each value against the one before it. A valid tree prints an increasing list. The first value that does not increase is where the validator stops.

A violation deep in the tree

Here is a tree that passes every direct-children check and still breaks the rule. The root is 10. Its left child is 5, and 5 has children 2 and 12. Its right child is 20.

        10
       /  \
      5    20
     / \
    2   12

Check the direct children first. Node 5 has 2 on its left, which is smaller, and 12 on its right, which is larger. Node 10 has 5 on its left, which is smaller, and 20 on its right, which is larger. Nodes 2, 12 and 20 are leaves. Every direct check passes.

Now run the range method. The root gets the window from negative infinity to positive infinity, and 10 fits. The left child 5 gets the window from negative infinity to 10, and 5 fits. The node 2 gets the window from negative infinity to 5, and 2 fits. The right child of 5 is 12. It sits in the left subtree of 10, so its window is the one from 5 to 10, and 12 is not inside that window. The check fails at 12.

The window explains the reason. The value 12 is larger than its parent 5, which looks fine on its own. But 12 is under the left side of 10, so it must also be smaller than 10. The window carries that limit down the tree, and the direct check never sees it.

The inorder method finds the same problem. Walking the tree in order prints 2, 5, 12, 10, 20. The value 10 comes after 12 but is smaller than it, so the sequence stops increasing at that point. The check sees the value 12 as the previous value when it reaches 10, and it returns false.

Inorder successor

The inorder successor of a value is the next value in sorted order. It is the smallest stored value that is strictly larger than the given value. The successor of 6 in the nine-node tree is 7. The successor of 14, the largest value, does not exist.

You need the successor for delete, and you need it for range questions such as "what is the next event after this time". The question is simple, but the code has a neat shape.

Walk down from the root toward the target, as a search would. Each time you move left, the current node is larger than the target. So it is a candidate: it might be the successor, or a smaller value on the left might be the real answer. Remember the last candidate you passed. When you move right, the current node is smaller than or equal to the target, so it is not a candidate, and you keep the old one.

The search path for 5 visits 8 and 6 as candidates, and 6 is the last candidate, so it is the successor

The picture shows the walk for 5 in a small tree. The walk starts at 8. Eight is larger than 5, so it is a candidate, and the walk goes left to 3. Three is smaller than 5, so the walk goes right to 6. Six is larger than 5, so it becomes the newest candidate, and the walk goes left to 4. Four is smaller than 5, so the walk goes right, and there is no node there. The last candidate, 6, is the answer.

Here is the program. It reads the values, then reads several queries and prints the successor of each one.

Type this into the Input box:

6
8 3 10 6 14 7
4
6
7
14
5

The output is:

7
8
none
6

Check each answer against the sorted list 3, 6, 7, 8, 10, 14. The successor of 6 is 7. The successor of 7 is 8. Nothing in the list is larger than 14, so the answer is none. For 5, the value 5 is not stored, but the successor still makes sense: it is the smallest stored value above 5, which is 6. The walk handles absent targets with no special case, and that is one of its strengths.

Read the if (target < root->val) line. When the target is smaller than the node, the node is a candidate. When the target is equal to or larger than the node, the node is not larger than the target, so the walk goes right and keeps the old candidate. Because the test is strict, a node equal to the target is never a candidate. That is what makes the successor strictly larger.

The predecessor is the mirror image. Walk down, and whenever you move right, record the current node as a candidate. Practice exercise 2 asks you to write it.

The successor walk is O(h) in time and O(1) in extra memory, because it moves one pointer and keeps one candidate.

Worked successor traces

Trace three successor queries on the nine-value tree from lesson 1. It has 8 at the root, with left subtree 3 (children 1 and 6, and 6 has children 4 and 7) and right subtree 10 (with right child 14, and 14 holding 13 on its left). Keep a note of the candidate after each step.

Query 7. Start at 8. Seven is smaller than 8, so 8 becomes the candidate, and the walk goes left to 3. Seven is larger than 3, so the walk goes right to 6. Seven is larger than 6, so the walk goes right to 7. Seven is not smaller than 7, so the walk goes right and falls off the tree. The last candidate is 8, so the successor is 8.

Query 13. Start at 8. Thirteen is larger than 8, so the walk goes right to 10 without setting a candidate. Thirteen is larger than 10, so the walk goes right to 14. Thirteen is smaller than 14, so 14 becomes the candidate, and the walk goes left to 13. Thirteen is not smaller than 13, so the walk goes right and falls off. The last candidate is 14.

Query 14. The walk goes from 8 to 10 to 14. At 14 the target is not smaller, so the walk goes right and falls off. No candidate was ever set, so the answer is none.

The query for 13 shows why the walk keeps going after it sets a candidate. The node holding 13 equals the target, so it is not a successor, but the walk still has to check it. The answer stays 14 because nothing smaller than 14 and larger than 13 exists in the tree.

Run the mirror walk for the predecessor of 7. Start at 8. Seven is smaller than 8, so the walk goes left to 3 without setting a candidate. Seven is larger than 3, so 3 becomes the candidate, and the walk goes right to 6. Seven is larger than 6, so 6 becomes the candidate, and the walk goes right to 7. Seven is not larger than 7, so the walk goes left and falls off. The last candidate is 6, so the predecessor is 6.

Finding the k-th smallest value

A common follow-up question is "return the k-th smallest value". You can answer it with the inorder walk, because the walk visits values in sorted order. Count the visits, and stop at the k-th one.

The standard way to write this is an iterative inorder walk with an explicit stack. A stack is a list where you add and remove items at one end, like a stack of plates. The stack holds the nodes you have passed on the way left but not yet visited. The walk goes as far left as it can, visits the node on top, and then moves right.

Type this into the Input box:

6
8 3 10 6 14 7
4
1
3
6
7

The output is:

3
7
14
-1

The sorted values are 3, 6, 7, 8, 10, 14. So the first is 3, the third is 7, the sixth is 14, and there is no seventh, which gives -1.

Trace the walk for k equal to 3. The tree is 8 with left child 3, 3 with right child 6, 6 with right child 7, and 8 with right child 10, which has right child 14. The walk pushes 8, then 3, and finds nothing to the left of 3. It pops 3 and visits it. The counter goes from 3 down to 2. The walk moves to the right child of 3, which is 6. It pushes 6, finds nothing to its left, pops it and visits it. The counter goes from 2 down to 1. The walk moves to the right child of 6, which is 7. It pushes 7, pops it and visits it. The counter goes from 1 down to 0, so the walk returns 7.

Notice that 8 is still on the stack when the answer is found. The walk visits nodes in sorted order, so the third visit is the third smallest value, and the stack holds the nodes it has not visited yet.

The walk stops early. For k equal to 1 it returns after the first visit, so it never touches the right side of the tree. That is why the cost is O(h + k): O(h) to reach the first value, then one step per visit.

What happens inside

The validator and the successor walk both use a pointer that moves down the tree, but they keep different kinds of memory.

The range validator keeps two long long values per frame on the call stack. Each recursive call has its own copy of lo and hi, so going left and going right do not interfere. The call stack grows to h frames, so the extra memory is O(h).

The inorder validator keeps one long long variable, prev, which lives in main. The reference long long& prev means every call works on that same variable. When a call sets prev = n->val, every other call sees the new value. This shared state is what makes the walk work, and it is also the reason you must reset prev before each new check.

The successor walk keeps one pointer, succ, which is the candidate. Its memory is fixed, O(1), no matter how big the tree is.

The k-th walk keeps a stack of pointers. The stack holds the nodes on the left spine of the current position, so its size is at most h. The stack is a real container on the heap, so its memory is O(h).

Common mistakes and what you see

Mistake 1: checking only direct children. This passes the trap tree and prints valid. The real output of the broken check on the trap tree is:

local check says valid

The tree is invalid, so this output is wrong. The fix is to pass bounds down, or to use the inorder walk. Remember that the rule is about whole subtrees.

Mistake 2: int sentinels. Starting the window at INT_MIN and INT_MAX with int rejects any tree that contains those values. The output of the broken version on a valid tree is invalid, with a trace whose first line shows the range starting at the root value. Use long long bounds, as the lesson does.

Mistake 3: using <= where the rule needs <. If the check is n->val < lo instead of n->val <= lo, a value equal to the bound is accepted. A tree with two 5s would pass, even though the rule forbids duplicates. Decide on your policy, then write the comparisons to match it.

Mistake 4: forgetting to reset the state. The inorder validator keeps prev between calls. If you run two checks in the same program and forget to reset prev, the second check starts with the last value of the first tree, and the answer can be wrong. Set it to LLONG_MIN before every check.

Mistake 5: returning the root as the successor. The candidate starts as nullptr, not as the root. If you start it at the root, a target larger than everything returns the root instead of none. Check the case of the largest value, where the answer must be none.

Mistake 6: walking the successor in the left subtree. The successor is in the right subtree when the node has one, or it is an ancestor otherwise. Searching only the left side returns a smaller value and breaks the rule.

Debugging walkthrough: a valid tree that is rejected

Suppose a validator rejects a tree that you know is valid. The first step is to ask which check failed. Print the bounds at each visit, as the broken int version did. The printed trace shows you the window at every node. If a node is rejected even though it sits inside its window, the bound is wrong. If a node is outside its window, the tree is genuinely invalid, and the trace shows which ancestor set the limit.

For the inorder version, print the value of prev before and after each node. The sequence should increase. The first place where it does not increase shows you the node that broke the order. Often that node is a left child that is larger than its ancestor, which is the trap from the start of this lesson.

Variations and edge cases

An empty tree is valid for both methods. The range check returns true at once, and the inorder check returns true because there is nothing to compare.

A single node is valid. Its window is unlimited.

Duplicates. If equal values are allowed on the left, make the upper bound inclusive and keep the lower bound strict. Practice exercise 3 asks you to write it.

A successor that is not stored. The successor code works for a target that is not in the tree, as the example with 5 showed. It returns the smallest stored value above the target.

The largest value. Its successor is none. The walk never sets a candidate, so succ stays nullptr.

Predecessor. The mirror image walks right and keeps candidates when it moves right.

Complexity

Every method depends on h, except the validators, which visit all n nodes. On a balanced tree of a million values, the successor takes about 20 steps. On a chain, it takes a million.

Interview questions and real-world uses

When you hear "validate a BST", say the rule first, then explain the trap. Name both methods. Write the range version, because it is the most common answer, and explain why long long is needed. If the interviewer asks what changes to allow duplicates, the answer is the bounds: one strict, one inclusive, as in practice exercise 3.

For the successor, expect a variant with parent pointers, where each node stores its parent. There the walk goes up instead of down. The down-walk in this lesson needs no parent pointers, which is why it is the standard answer when the tree has none.

A good way to present validation in an interview is to show the trap first. Name the wrong idea, draw the tree that defeats it, and explain why the direct check passes. Then give the fix as the window method, with the bounds written out at each step. Finish with the inorder method as a second answer. Both run in O(n). Mention that the inorder version stops at the first failure and needs only one saved value, which is a useful point when the interviewer asks about memory. Candidates who test their own first answer on a small example usually score higher than candidates who only recite a correct method.

In real systems, successor queries answer questions such as "what is the next scheduled job after this time". Index systems use the same operations on their trees. Validation matters when data is loaded from a file, because a corrupt file can break the rule silently and make later searches return wrong answers.

Common follow-up questions

What changes if every node stores a parent pointer? The walk can start at the node itself, so you do not need the value. If the node has a right child, the successor is the leftmost node of that right subtree, which is the same rule as the delete in lesson 2. If the node has no right child, go up. Keep going up while you are a right child of your parent. The first parent you reach from its left side is the successor. If you reach the root without that, the node was the largest, and the answer is none. This version costs O(h) in the worst case, and it needs the extra pointer in every node.

Why not sort the values and binary search instead? A sorted array answers "what comes next" with one binary search, which costs O(log n), but it cannot take inserts or deletes without shifting the array. The BST walk costs O(h) and supports changes in the same tree. For a fixed set of values, the sorted array is simpler and fast. For a set that changes, the tree is the right structure, and it stays balanced only if you add balancing, as lesson 5 does.

Does the walk work when the target is larger than every value? Yes. Every comparison goes right, no candidate is set, and the walk falls off the tree. The function returns nullptr, which the caller must check before reading ->val. Forgetting that check is the most common crash in successor code.

Practice

Try these before you open the solutions. Compile with g++ -std=c++17 -Wall -g -fsanitize=address,undefined to catch mistakes early.

1. Easy. Write int kthSmallestRec(Node* root, int& k) using recursion. It returns the k-th smallest value, or -1 if there are fewer than k. The argument k counts down as the walk visits nodes. Hint: recurse left, then count the node, then recurse right.

int kthSmallestRec(Node* n, int& k) {
    if (!n) return -1;
    int found = kthSmallestRec(n->left, k);
    if (found != -1) return found;
    k--;
    if (k == 0) return n->val;
    return kthSmallestRec(n->right, k);
}

2. Easy. Write Node* predecessor(Node* root, int target) that returns the node with the largest value strictly smaller than target, or nullptr. Hint: walk right whenever the node is smaller than the target, and keep it as a candidate.

Node* predecessor(Node* root, int target) {
    Node* pred = nullptr;
    while (root) {
        if (root->val < target) {
            pred = root;               // smaller than target: a candidate
            root = root->right;        // look for something closer
        } else {
            root = root->left;         // not smaller, so go left
        }
    }
    return pred;
}

3. Medium. Write bool isBSTAllowDup(Node* root) that checks the BST rule when equal values are allowed on the left side of a node, and the right side stays strict. Hint: one bound should be strict and the other inclusive.

bool validAllowDup(Node* n, long long lo, long long hi) {
    if (!n) return true;
    if (n->val <= lo || n->val > hi) return false;   // lo is strict, hi is inclusive
    return validAllowDup(n->left, lo, n->val) && validAllowDup(n->right, n->val, hi);
}
 
bool isBSTAllowDup(Node* root) {
    return validAllowDup(root, LLONG_MIN, LLONG_MAX);
}

4. Medium. Write int countViolations(Node* root) that returns how many nodes lie outside their allowed range. A node counts once, even if it breaks a bound from more than one ancestor. Hint: do not stop at the first failure.

int countViolations(Node* n, long long lo, long long hi) {
    if (!n) return 0;
    int here = (n->val <= lo || n->val >= hi) ? 1 : 0;
    return here + countViolations(n->left, lo, n->val) + countViolations(n->right, n->val, hi);
}
 
int countViolations(Node* root) {
    return countViolations(root, LLONG_MIN, LLONG_MAX);
}

5. Medium. Write bool isStrictlyIncreasingInorder(Node* root) using an explicit stack, without recursion. Hint: pop nodes in order, and keep the last value you popped.

bool isStrictlyIncreasingInorder(Node* root) {
    stack<Node*> st;
    Node* cur = root;
    long long prev = LLONG_MIN;
    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();
        if (cur->val <= prev) return false;
        prev = cur->val;
        cur = cur->right;
    }
    return true;
}

6. Medium. Write void printGreater(Node* root, int x) that prints every stored value larger than x, in increasing order, without visiting the subtrees that cannot contain such values. Hint: if the node is not larger than x, its left subtree is smaller too, so skip it.

void printGreater(Node* n, int x) {
    if (!n) return;
    if (n->val > x) printGreater(n->left, x);   // left values may still be larger than x
    if (n->val > x) cout << n->val << " ";
    printGreater(n->right, x);                  // the right side is always at least as large
}

7. Medium. Write int secondLargest(Node* root) that returns the second largest value. Assume the tree has at least two nodes. Hint: the largest node is the rightmost one. The second largest is either its parent or the largest value in its left subtree.

int secondLargest(Node* root) {
    Node* parent = nullptr;
    Node* cur = root;
    while (cur->right) {           // walk to the largest node, remembering its parent
        parent = cur;
        cur = cur->right;
    }
    if (cur->left) {               // the largest value in the left subtree
        Node* m = cur->left;
        while (m->right) m = m->right;
        return m->val;
    }
    return parent->val;            // otherwise the parent is the second largest
}

8. Hard. Two nodes of a valid BST were swapped by mistake. Write void recoverBST(Node* root) that swaps their values back, using only the inorder walk. Hint: during the inorder walk, a swapped pair shows up as one or two places where the order goes down. The first wrong node is the larger value of the first drop, and the second wrong node is the smaller value of the last drop.

void recoverBST(Node* root) {
    Node* first = nullptr;
    Node* second = nullptr;
    Node* prev = nullptr;
    stack<Node*> st;
    Node* cur = root;
    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();
        if (prev && prev->val > cur->val) {
            if (!first) first = prev;     // the first drop: the larger value is wrong
            second = cur;                 // the last drop: the smaller value is wrong
        }
        prev = cur;
        cur = cur->right;
    }
    if (first && second) {
        int tmp = first->val;
        first->val = second->val;
        second->val = tmp;
    }
}

9. Hard. Write bool hasPairWithSum(Node* root, int target) that returns true when two different stored values add up to target. Hint: an inorder walk gives a sorted list, and a sorted list lets you use two pointers, one at each end.

void collectInorder(Node* n, vector<int>& out) {
    if (!n) return;
    collectInorder(n->left, out);
    out.push_back(n->val);
    collectInorder(n->right, out);
}
 
bool hasPairWithSum(Node* root, int target) {
    vector<int> a;
    collectInorder(root, a);              // sorted, because it is a BST
    int i = 0, j = (int)a.size() - 1;
    while (i < j) {
        long long s = (long long)a[i] + a[j];
        if (s == target) return true;
        if (s < target) i++;
        else j--;
    }
    return false;
}

10. Medium. Write Node* succRec(Node* root, int x) that returns the smallest value greater than x, using recursion and no loop. Hint: if the node is not larger than x, the answer is on the right. If it is larger, the answer is on the left if there is one, and the node itself otherwise.

Node* succRec(Node* root, int x) {
    if (!root) return nullptr;
    if (root->val <= x) return succRec(root->right, x);
    Node* left = succRec(root->left, x);
    return left ? left : root;
}

What you now know

• A check against direct children is not enough. Each node must be inside a window set by all its ancestors.
• Use long long bounds, or a long long previous value, so that INT_MIN and INT_MAX are real values, not sentinels.
• An inorder walk of a valid BST is strictly increasing, which gives a second validator.
• The inorder successor is the last candidate you pass while walking down and going left.
• The k-th smallest value comes from an inorder walk with a stack, and it stops early.
• Check each method's edge cases: an empty tree, one node, duplicates and a target that is not stored.

The next lesson asks why a plain BST can become a chain, and shows how a sorted array can become a balanced tree.