C++ code with explanation and annotation, using nonrecursive inorder traversal

  • 0

    To solve this problem, you need to know the definition of BST (binary search tree), here is the wiki link: https://en.wikipedia.org/wiki/Binary_search_tree
    According to the definition of BST, the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.
    If you know that the inorder traversal of a BST tree is an ascending order sequence (you should verify this by yourself), then we only need to output the k-th elements in the inorder traversal sequence.
    Here is my code, a implementation of nonrecursive inorder traversal, you can very easily to implement the nonrecursive preorder and postorder traversal based on this code.

    class Solution {
        int kthSmallest(TreeNode* root, int k) {
            if( root == NULL ){   // null, return a special value
                return 0;
            int count = 0;  // how many elements we have record, if count==k, then stop
            int min = root->val; // for the case when k is larger than the number of nodes
            stack<pair<TreeNode*, bool> > s;  // the boolean variable denotes whether this node is visited or not
            s.push(make_pair(root, false));  // initialize the stack
                pair<TreeNode*, bool> p;
                p = s.top();
                if( p.first == NULL ){
                if( p.second == true ){  // visited, output
                    if( count == k ){
                        min = p.first->val;
                    if( min < p.first->val ){ // record minimum number
                        min = p.first->val;
                    s.push(make_pair(p.first->right, false));   // note, this is slightly different from the recursive inorder traversal implementation
            return min;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.