Kth Smallest Element in a BST

🎯

Kth Smallest Element in a BST

mediumTREEAmazonGoogleFacebook

Imagine you have a sorted collection of numbers stored efficiently in a binary search tree, and you want to quickly find the kth smallest number without flattening the entire tree.

💡 This problem tests understanding of BST properties and tree traversal. Beginners often struggle because they try to flatten the tree fully or don't leverage the BST's sorted nature, leading to inefficient solutions.

📋

Problem Statement

Given the root of a binary search tree (BST) and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

The number of nodes in the tree is n, where 1 ≤ n ≤ 10^51 ≤ k ≤ nNode values are unique integers

💡

Example

Input"root = [3,1,4,null,2], k = 1"

Output1

The in-order traversal of the BST is [1,2,3,4]. The 1st smallest element is 1.

Input"root = [5,3,6,2,4,null,null,1], k = 3"

Output3

In-order traversal: [1,2,3,4,5,6]. The 3rd smallest element is 3.

• k equals 1 (smallest element) → returns smallest node value
• k equals n (largest element) → returns largest node value
• Tree with only one node → returns that node's value regardless of k=1
• Skewed tree (all nodes only left or right) → traversal still works correctly

⚠️

Common Mistakes

Not stopping traversal early in recursive approach

Unnecessary traversal of entire tree, leading to timeouts on large inputs

✅ Add a condition to stop recursion once kth element is found

Using k as zero-based index instead of one-based

Returns wrong element or index out of range error

✅ Adjust indexing by subtracting 1 when accessing list or counting nodes

Not handling null nodes properly in recursion

Runtime errors or infinite recursion

✅ Add base case to return when node is null

Confusing inorder traversal order

Incorrect element returned because traversal order is wrong

✅ Remember inorder is left, root, right for BST to get sorted order

Using recursion without considering stack overflow on skewed trees

Stack overflow error on deep trees

✅ Use iterative approach with explicit stack to avoid recursion limits

🧠

Brute Force (Inorder Traversal with Full List)

💡 This approach exists to build intuition by fully traversing the BST and collecting all elements in sorted order, which is straightforward but not optimal for large trees.

Intuition

Perform an inorder traversal to get all node values in sorted order, then return the kth element from the list.

Algorithm

1. Traverse the BST inorder and store all node values in a list.
2. After traversal, the list is sorted because of BST properties.
3. Return the element at index k-1 from the list.

💡 The main challenge is understanding that inorder traversal of BST yields sorted order, making it easy to pick kth smallest after traversal.

</>

Code

from typing import Optional, List

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

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    def inorder(node: Optional[TreeNode], acc: List[int]):
        if not node:
            return
        inorder(node.left, acc)
        acc.append(node.val)
        inorder(node.right, acc)

    elements = []
    inorder(root, elements)
    return elements[k-1]

# Driver code to test
if __name__ == '__main__':
    # Construct BST: [3,1,4,null,2]
    root = TreeNode(3)
    root.left = TreeNode(1)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    print(kthSmallest(root, 1))  # Output: 1

Line Notes

def inorder(node: Optional[TreeNode], acc: List[int]):Defines helper function to collect nodes inorder

if not node:Base case to stop recursion at leaf's child

inorder(node.left, acc)Traverse left subtree first to get smaller elements

acc.append(node.val)Add current node's value after left subtree to maintain sorted order

inorder(node.right, acc)Traverse right subtree for larger elements

elements = []Initialize list to store inorder traversal results

inorder(root, elements)Start traversal from root

return elements[k-1]Return kth smallest element from sorted list

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> elements = new ArrayList<>();
        inorder(root, elements);
        return elements.get(k - 1);
    }

    private void inorder(TreeNode node, List<Integer> acc) {
        if (node == null) return;
        inorder(node.left, acc);
        acc.add(node.val);
        inorder(node.right, acc);
    }

    // Driver code
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        Solution sol = new Solution();
        System.out.println(sol.kthSmallest(root, 1)); // Output: 1
    }
}

Line Notes

List<Integer> elements = new ArrayList<>();Create list to hold inorder traversal

inorder(root, elements);Start inorder traversal from root

if (node == null) return;Base case to stop recursion

acc.add(node.val);Add current node value after left subtree traversal

return elements.get(k - 1);Return kth smallest element from sorted list

public static void main(String[] args)Driver code to test the solution

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void inorder(TreeNode* node, vector<int>& acc) {
        if (!node) return;
        inorder(node->left, acc);
        acc.push_back(node->val);
        inorder(node->right, acc);
    }

    int kthSmallest(TreeNode* root, int k) {
        vector<int> elements;
        inorder(root, elements);
        return elements[k - 1];
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);
    Solution sol;
    cout << sol.kthSmallest(root, 1) << endl; // Output: 1
    return 0;
}

Line Notes

void inorder(TreeNode* node, vector<int>& acc)Helper function to collect nodes inorder

if (!node) return;Stop recursion at null nodes

inorder(node->left, acc);Traverse left subtree first

acc.push_back(node->val);Add current node value after left subtree

return elements[k - 1];Return kth smallest element from sorted vector

int main()Driver code to test the solution

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function kthSmallest(root, k) {
    const elements = [];
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        elements.push(node.val);
        inorder(node.right);
    }
    inorder(root);
    return elements[k - 1];
}

// Driver code
const root = new TreeNode(3);
root.left = new TreeNode(1);
root.right = new TreeNode(4);
root.left.right = new TreeNode(2);
console.log(kthSmallest(root, 1)); // Output: 1

Line Notes

function inorder(node) {Helper function to traverse tree inorder

if (!node) return;Base case to stop recursion

inorder(node.left);Traverse left subtree first

elements.push(node.val);Add current node value after left subtree

return elements[k - 1];Return kth smallest element from sorted array

console.log(kthSmallest(root, 1));Test the function with example input

⏱

Complexity

TimeO(n)

SpaceO(n)

We visit every node once during inorder traversal, and store all n nodes in a list.

💡 For n=20 nodes, this means about 20 operations to traverse and store, which is manageable but not efficient for very large trees.

Interview Verdict: Accepted but not optimal for large trees

This approach works but uses extra space and time; interviewers expect more efficient solutions.

🧠

Optimized Recursive Inorder with Early Stopping

💡 This approach improves on brute force by stopping traversal once the kth smallest element is found, saving unnecessary work.

Intuition

Perform inorder traversal but keep track of how many nodes have been visited; stop and return as soon as kth node is reached.

Algorithm

1. Initialize a counter to track number of nodes visited.
2. Traverse the BST inorder recursively.
3. Increment counter when visiting a node.
4. When counter equals k, record the node's value and stop traversal.
5. Return the recorded value.

💡 The key is to stop recursion early to avoid traversing the entire tree unnecessarily.

</>

Code

from typing import Optional

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

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    count = 0
    result = None

    def inorder(node: Optional[TreeNode]):
        nonlocal count, result
        if not node or result is not None:
            return
        inorder(node.left)
        count += 1
        if count == k:
            result = node.val
            return
        inorder(node.right)

    inorder(root)
    return result

# Driver code
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(1)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    print(kthSmallest(root, 1))  # Output: 1

Line Notes

count = 0Initialize counter for visited nodes

result = NoneStore kth smallest value once found

if not node or result is not None:Stop recursion if node is null or kth element found

count += 1Increment count when visiting a node

if count == k:Check if current node is kth smallest

result = node.valRecord kth smallest value

inorder(root)Start traversal from root

return resultReturn the found kth smallest element

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    private int count = 0;
    private int result = -1;

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

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

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        Solution sol = new Solution();
        System.out.println(sol.kthSmallest(root, 1)); // Output: 1
    }
}

Line Notes

private int count = 0;Counter for visited nodes

private int result = -1;Store kth smallest value once found

if (node == null || result != -1) return;Stop recursion if node null or kth found

count++;Increment count when visiting node

if (count == k)Check if current node is kth smallest

result = node.val;Record kth smallest value

inorder(root, k);Start traversal from root

return result;Return kth smallest element

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    int count = 0;
    int result = -1;
public:
    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;
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);
    Solution sol;
    cout << sol.kthSmallest(root, 1) << endl; // Output: 1
    return 0;
}

Line Notes

int count = 0;Counter for nodes visited

int result = -1;Store kth smallest value once found

if (!node || result != -1) return;Stop recursion if node null or kth found

count++;Increment count when visiting node

if (count == k)Check if current node is kth smallest

result = node->val;Record kth smallest value

inorder(root, k);Start traversal from root

return result;Return kth smallest element

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function kthSmallest(root, k) {
    let count = 0;
    let result = null;

    function inorder(node) {
        if (!node || result !== null) return;
        inorder(node.left);
        count++;
        if (count === k) {
            result = node.val;
            return;
        }
        inorder(node.right);
    }

    inorder(root);
    return result;
}

// Driver code
const root = new TreeNode(3);
root.left = new TreeNode(1);
root.right = new TreeNode(4);
root.left.right = new TreeNode(2);
console.log(kthSmallest(root, 1)); // Output: 1

Line Notes

let count = 0;Counter for visited nodes

let result = null;Store kth smallest value once found

if (!node || result !== null) return;Stop recursion if node null or kth found

count++;Increment count when visiting node

if (count === k)Check if current node is kth smallest

result = node.val;Record kth smallest value

inorder(root);Start traversal from root

return result;Return kth smallest element

⏱

Complexity

TimeO(H + k)

SpaceO(H)

In the best case, we only traverse down to kth node, where H is tree height. Space is recursion stack height.

💡 For balanced trees with height ~log n, and k=10, this means about 10-15 operations, much faster than full traversal.

Interview Verdict: Accepted and efficient for balanced trees

This approach is a good balance of simplicity and efficiency, often preferred in interviews.

🧠

Iterative Inorder Traversal Using Stack

💡 This approach uses an explicit stack to simulate recursion, which is often preferred in interviews to avoid recursion overhead and stack overflow.

Intuition

Use a stack to traverse the BST inorder iteratively, popping nodes and counting until kth smallest is found.

Algorithm

1. Initialize an empty stack and set current node to root.
2. While current is not null or stack is not empty:
3. Push all left children of current onto stack.
4. Pop from stack, increment count.
5. If count equals k, return popped node's value.
6. Move to right child of popped node.

💡 The stack keeps track of nodes to visit next, simulating recursion but with explicit control.

</>

Code

from typing import Optional

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

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

# Driver code
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(1)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    print(kthSmallest(root, 1))  # Output: 1

Line Notes

stack = []Initialize stack to simulate recursion

while current or stack:Continue while nodes remain to visit

while current:Go as left as possible pushing nodes

stack.append(current)Push current node to stack before going left

current = stack.pop()Pop node to visit in inorder sequence

count += 1Increment count for visited node

if count == k:Check if kth smallest found

current = current.rightMove to right subtree after visiting node

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        int count = 0;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            count++;
            if (count == k) return current.val;
            current = current.right;
        }
        return -1; // Should never reach here if k valid
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        Solution sol = new Solution();
        System.out.println(sol.kthSmallest(root, 1)); // Output: 1
    }
}

Line Notes

Stack<TreeNode> stack = new Stack<>();Stack to simulate recursion

while (current != null || !stack.isEmpty()) {Traverse while nodes remain

stack.push(current);Push current node before going left

current = stack.pop();Pop node to visit in inorder

count++;Increment count for visited node

if (count == k) return current.val;Return kth smallest when found

current = current.right;Move to right subtree after visiting node

return -1;Fallback return, should not happen if k valid

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> stk;
        TreeNode* current = root;
        int count = 0;

        while (current || !stk.empty()) {
            while (current) {
                stk.push(current);
                current = current->left;
            }
            current = stk.top();
            stk.pop();
            count++;
            if (count == k) return current->val;
            current = current->right;
        }
        return -1; // Should not happen
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);
    Solution sol;
    cout << sol.kthSmallest(root, 1) << endl; // Output: 1
    return 0;
}

Line Notes

stack<TreeNode*> stk;Stack to simulate recursion

while (current || !stk.empty()) {Traverse while nodes remain

stk.push(current);Push current node before going left

current = stk.top();Pop node to visit in inorder

count++;Increment count for visited node

if (count == k) return current->val;Return kth smallest when found

current = current->right;Move to right subtree after visiting node

return -1;Fallback return, should not happen if k valid

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function kthSmallest(root, k) {
    const stack = [];
    let current = root;
    let count = 0;

    while (current !== null || stack.length > 0) {
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        count++;
        if (count === k) return current.val;
        current = current.right;
    }
    return -1; // Should not happen
}

// Driver code
const root = new TreeNode(3);
root.left = new TreeNode(1);
root.right = new TreeNode(4);
root.left.right = new TreeNode(2);
console.log(kthSmallest(root, 1)); // Output: 1

Line Notes

const stack = [];Stack to simulate recursion

while (current !== null || stack.length > 0) {Traverse while nodes remain

stack.push(current);Push current node before going left

current = stack.pop();Pop node to visit in inorder

count++;Increment count for visited node

if (count === k) return current.val;Return kth smallest when found

current = current.right;Move to right subtree after visiting node

return -1;Fallback return, should not happen if k valid

⏱

Complexity

TimeO(H + k)

SpaceO(H)

Stack stores nodes along path; we visit nodes until kth smallest found. H is tree height.

💡 For balanced trees, this is efficient and avoids recursion stack overhead.

Interview Verdict: Accepted and preferred iterative solution

Interviewers often prefer iterative solutions to test understanding of traversal mechanics.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, approach 2 or 3 is best: efficient and easy to implement. Approach 1 is good to mention but not code.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	Yes (due to recursion depth)	Yes	Mention only - never code
2. Optimized Recursive Inorder with Early Stopping	O(H + k)	O(H)	Yes (for very deep trees)	Yes	Good to code if recursion allowed
3. Iterative Inorder Traversal Using Stack	O(H + k)	O(H)	No	Yes	Preferred approach to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, optimize step-by-step, and finally code the best approach.

How to Present

Clarify input format and constraints.State the brute force approach: full inorder traversal and indexing.Explain inefficiency and propose early stopping recursion.Discuss iterative stack-based traversal as an alternative.Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of BST properties, inorder traversal, recursion vs iteration, and optimization skills.

Common Follow-ups

• What if the BST is modified frequently? → Use augmented BST with node counts.
• How to find kth largest element? → Reverse inorder traversal.

💡 These follow-ups test your ability to adapt the solution to variations and optimize for dynamic data.

🔍

Pattern Recognition

When to Use

1) Input is a BST, 2) Need kth smallest/largest element, 3) Sorted order required, 4) Traversal or counting needed

Signature Phrases

kth smallest elementbinary search treeinorder traversal

NOT This Pattern When

Problems asking for path sums or subtree properties without order requirements

Similar Problems

Kth Largest Element in a BST - same pattern but reversed traversalClosest Binary Search Tree Value - uses BST traversal to find closest value

Practice

1. Consider the following Python code snippet for balancing a BST using inorder traversal and iterative construction. Given the BST with nodes 1, 2, 3 inserted in that order, what is the value of the root node after balancing?

easy

A. 1

B. 2

C. 3

D. None (empty tree)

Solution

1. Step 1: Perform inorder traversal on BST with nodes 1, 2, 3

   Inorder traversal yields nodes in sorted order: [1, 2, 3].

2. Step 2: Iteratively build balanced BST choosing middle node

   Middle index is 1 (0-based), so node with value 2 becomes root.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Middle of [1,2,3] is 2 -> root value 2 [OK]

Hint: Middle element of sorted nodes becomes root [OK]

Common Mistakes:

• Choosing left or right middle always, skewing tree
• Confusing preorder with inorder traversal results
• Forgetting to reset left/right pointers causing cycles

2. Consider the following BSTIterator implementation using Morris traversal:

class BSTIterator:
    def __init__(self, root):
        self.current = root
        self.next_val = None
        self._advance()

    def _advance(self):
        while self.current:
            if not self.current.left:
                self.next_val = self.current.val
                self.current = self.current.right
                return
            else:
                pre = self.current.left
                while pre.right and pre.right != self.current:
                    pre = pre.right
                if not pre.right:
                    pre.right = self.current
                    self.current = self.current.left
                else:
                    pre.right = None
                    self.next_val = self.current.val
                    self.current = self.current.right

Given the BST with nodes 2 (root), 1 (left child), and 3 (right child), what is the value of next_val after the first call to _advance() during initialization?

easy

A. 3

B. 2

C. 1

D. null

Solution

1. Step 1: Trace _advance() starting at root=2

   Since root has a left child (1), find predecessor of 2 in left subtree: node 1 has no right child, so set 1.right = 2 and move current to 1.

2. Step 2: At current=1, no left child, so set next_val=1 and move current to 1.right which points back to 2 (thread).

   Return from _advance() with next_val=1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   First inorder element is 1, matches next_val after first advance [OK]

Hint: Morris traversal first yields leftmost node [OK]

Common Mistakes:

• Assuming next_val is root value initially
• Forgetting thread creation
• Confusing next_val with current node

3. Consider the following code snippet implementing the optimal iterative approach to convert a BST to a Greater Tree. Given the BST with nodes [2, 1, 3], what is the value of the root node after the function completes?

easy

A. 5

B. 6

C. 3

D. 4

Solution

1. Step 1: Trace reverse inorder traversal order

   Nodes visited in order: 3, 2, 1.

2. Step 2: Accumulate sums and update nodes

   acc_sum=0 initially. - Visit 3: acc_sum=3, node.val=3 - Visit 2: acc_sum=3+2=5, node.val=5 - Visit 1: acc_sum=5+1=6, node.val=6 Root node was 2, updated to 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Root node value after update is 5 [OK]

Hint: Reverse inorder sums nodes from largest to smallest [OK]

Common Mistakes:

• Confusing traversal order and updating nodes too early
• Off-by-one errors in accumulating sums
• Misidentifying which node is root after updates

4. 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

5. What is the average time complexity per call of next() in the Morris traversal based BST Iterator, assuming the BST has n nodes?

medium

A. O(1) amortized per next() call because each edge is visited at most twice.

B. O(n) per next() call because each call may traverse the entire tree.

C. O(h) per next() call where h is the tree height due to traversing left children.

D. O(log n) per next() call assuming a balanced BST and stack usage.

Solution

1. Step 1: Understand Morris traversal edge visits

   Each edge in the BST is visited at most twice: once to create a thread and once to remove it.

2. Step 2: Calculate amortized cost per next()

   Since total work is O(n) for n nodes, and there are n calls to next(), average cost per call is O(1) amortized.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) per next() matches Morris traversal properties [OK]

Hint: Morris traversal visits edges twice total [OK]

Common Mistakes:

• Assuming worst-case O(n) per call
• Confusing with stack-based O(h)
• Ignoring amortized analysis