Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

Tree Iterator Problem

Problem Statement

Implement an iterator over a binary tree with integer values. Your iterator will be initialized with the root node.

1. next() method must return the next number in the in-order traversal of the tree.

2. hasNext() method must return whether the next element exists.

Both methods must run in average O(1) time and use O(h) memory, where h is the height of the given tree.

Example

Input:

          200

          /    \

       100  300

Output: [100, 200, 300]

Notes

Input Parameters: There is only one argument named root denoting the root of the input tree.

Output: There is nothing to return as a whole. What the given method will do is described below:

Constructor/initializer: Initialize the iterator.

next(): Returns an integer denoting the next node value.

hasNext(): Returns a boolean denoting the next node's presence.

Constraints:

• 1

• -10^9

Solution

We provided one optimal solution.

optimal_solution.cpp:

Iterator must iterate from the leftmost to the rightmost node so that the nodes are traversed in-order. The leftmost node of a tree is the first element in the in-order traversal of a binary tree, so while initializing, we pushed root, root’s left child, root’s left child’s left child until we reach the leftmost node of the tree. After initialization, the leftmost node is at the top of the stack. When next() method is invoked, the top element from the stack is popped. As all left nodes are pushed from current top node, we push all left nodes starting from the top node’s right child. This process continues until all nodes are traversed and popped from the stack. For better understanding, please take a look at the solution.

Time Complexity:

O(n) where n is the number of nodes in the tree.

As we are iterating over all the nodes once, time complexity will be O(n).

Auxiliary Space:

O(h) where h is the height of the tree.

As we are using a stack to store nodes to be returned later and maximum nodes at a time will be h where h is the height of the tree, auxiliary space will be O(h). In the worst case, h will be equal to n such as left skewed or right skewed tree. So, the auxiliary space used in the worst case is O(h).

Space Complexity:

O(n) where n is the number of nodes in the tree.

As to store given tree it will take O(n) space and auxiliary

space is O(n) hence space complexity is O(n) + O(n) = O(n).


// -------- START --------
/*
    Complete the following methods
*/

class BTIterator{
private:
    stack iteratorStack;
    // insert all the left child into the stack rcursively
    void insertLeftNodes(TreeNode *root){
        while(root != NULL){
            iteratorStack.push(root);
            root = root->left_ptr;
        }
    }

public:
    // constructor
    BTIterator(TreeNode *root){
        // insert all the left nodes of current subtree
        insertLeftNodes(root);
    }
    
    // Check whether iterator has reached to the end
    bool hasNext(){
        return (!iteratorStack.empty());
    }

    // return the next smallest element of the tree
    int next(){
        // fetch the current smallest element
        TreeNode *currentRoot = iteratorStack.top();
        // remove it from the iterator
        iteratorStack.pop();
        // insert all the left left nodes of it's rigth subtree into the stack
        insertLeftNodes(currentRoot->right_ptr);
        // return current node value
        return currentRoot->val;
    }
};

// -------- END --------

Try yourself in the Editor

Note: Input and Output will already be taken care of.

Tree Iterator Problem

Problem Statement

Implement an iterator over a binary tree with integer values. Your iterator will be initialized with the root node.

1. next() method must return the next number in the in-order traversal of the tree.

2. hasNext() method must return whether the next element exists.

Both methods must run in average O(1) time and use O(h) memory, where h is the height of the given tree.

Example

Input:

          200

          /    \

       100  300

Output: [100, 200, 300]

Notes

Input Parameters: There is only one argument named root denoting the root of the input tree.

Output: There is nothing to return as a whole. What the given method will do is described below:

Constructor/initializer: Initialize the iterator.

next(): Returns an integer denoting the next node value.

hasNext(): Returns a boolean denoting the next node's presence.

Constraints:

• 1

• -10^9

Solution

We provided one optimal solution.

optimal_solution.cpp:

Iterator must iterate from the leftmost to the rightmost node so that the nodes are traversed in-order. The leftmost node of a tree is the first element in the in-order traversal of a binary tree, so while initializing, we pushed root, root’s left child, root’s left child’s left child until we reach the leftmost node of the tree. After initialization, the leftmost node is at the top of the stack. When next() method is invoked, the top element from the stack is popped. As all left nodes are pushed from current top node, we push all left nodes starting from the top node’s right child. This process continues until all nodes are traversed and popped from the stack. For better understanding, please take a look at the solution.

Time Complexity:

O(n) where n is the number of nodes in the tree.

As we are iterating over all the nodes once, time complexity will be O(n).

Auxiliary Space:

O(h) where h is the height of the tree.

As we are using a stack to store nodes to be returned later and maximum nodes at a time will be h where h is the height of the tree, auxiliary space will be O(h). In the worst case, h will be equal to n such as left skewed or right skewed tree. So, the auxiliary space used in the worst case is O(h).

Space Complexity:

O(n) where n is the number of nodes in the tree.

As to store given tree it will take O(n) space and auxiliary

space is O(n) hence space complexity is O(n) + O(n) = O(n).


// -------- START --------
/*
    Complete the following methods
*/

class BTIterator{
private:
    stack iteratorStack;
    // insert all the left child into the stack rcursively
    void insertLeftNodes(TreeNode *root){
        while(root != NULL){
            iteratorStack.push(root);
            root = root->left_ptr;
        }
    }

public:
    // constructor
    BTIterator(TreeNode *root){
        // insert all the left nodes of current subtree
        insertLeftNodes(root);
    }
    
    // Check whether iterator has reached to the end
    bool hasNext(){
        return (!iteratorStack.empty());
    }

    // return the next smallest element of the tree
    int next(){
        // fetch the current smallest element
        TreeNode *currentRoot = iteratorStack.top();
        // remove it from the iterator
        iteratorStack.pop();
        // insert all the left left nodes of it's rigth subtree into the stack
        insertLeftNodes(currentRoot->right_ptr);
        // return current node value
        return currentRoot->val;
    }
};

// -------- END --------

Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Accelerate your Interview prep with Tier-1 tech instructors
blue tick
360° courses that have helped 14,000+ tech professionals
blue tick
100% money-back guarantee*
Register for Webinar

Recommended Posts

All Posts