Facebook

www.facebook.com

Interview Question

Software Engineer Interview

Create an iterator to traverse a binary tree. When the next

  function is called on the binary tree return the value at the next node as if you are doing an inorder traversal of the tree. Restrictions: Nodes do not have pointers to their parent node and you can't use recursion.
Answer

Interview Answer

1 Answer

1

class TreeNode
{
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : val(val), left(NULL), right(NULL) {}
};

class TreeIterator
{
private:
    stack<TreeNode*> stackA;

public:
    TreeIterator(TreeNode *root = NULL){
        while (root){
            stackA.push(root);
            root = root->left;
        }
    }

    TreeNode* getNext(){
        if (stackA.empty()) return NULL;

        TreeNode *target = stackA.top(); stackA.pop();
        TreeNode *node = target->right;
        while (node){
            stackA.push(node);
            node = node->left;
        }
        return target;
    }
};

My codes of the iterator implementation on Oct 5, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.