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


  • 0
    E

    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 {
    public:
        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
            while(!s.empty()){
                pair<TreeNode*, bool> p;
                p = s.top();
                s.pop();
                if( p.first == NULL ){
                    continue; 
                }
                if( p.second == true ){  // visited, output
                    count++;
                    if( count == k ){
                        min = p.first->val;
                        break;
                    }
                    if( min < p.first->val ){ // record minimum number
                        min = p.first->val;
                    }
                    continue;
                }
                else{
                    s.push(make_pair(p.first->right, false));   // note, this is slightly different from the recursive inorder traversal implementation
                    s.push(make_pair(p.first,true));
                    s.push(make_pair(p.first->left,false));
                }
            }
            return min;
        }
    };
    

Log in to reply
 

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