# Binary Search Tree Iterator

##### Problem

Implement the `BSTIterator` class that represents an iterator over the in-order traversal of a binary search tree (BST):

• `BSTIterator(TreeNode root)` Initializes an object of the `BSTIterator` class. The `root` of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
• `boolean hasNext()` Returns `true` if there exists a number in the traversal to the right of the pointer, otherwise returns `false`.
• `int next()` Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to `next()` will return the smallest element in the BST.

You may assume that `next()` calls will always be valid. That is, there will be at least a next number in the in-order traversal when `next()` is called.

Example 1:

```Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
```

[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); bSTIterator.next(); // return 3 bSTIterator.next(); // return 7 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 9 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 15 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 20 bSTIterator.hasNext(); // return False

Constraints:

• The number of nodes in the tree is in the range `[1, 105]`.
• `0 <= Node.val <= 106`
• At most `105` calls will be made to `hasNext`, and `next`.

• Could you implement `next()` and `hasNext()` to run in average `O(1)` time and use `O(h)` memory, where `h` is the height of the tree?
##### Solution

In inorder traversal, an iterator traverses to the left first, then (when there is no left child left) prints (or do something else with) the value and then traverses right. We have to mainly think about the implementation of the next() function of an iterator, as it is the most critical one.

Since the tree is already built, in the constructor of iterator we can use a stack and traverse to the left end of the tree and push all the left children in the stack. So, when someone will call next(), we can simply return the top of the stack, right? Because, when the iterator tries to find a next element, it traverses all the way back to the left of the tree and returns the left most child which we already did during the construction period and pushed all left children to the stack.

Is our job done? Not yet! We know the left-most leaf node has no children. But what about its parent node? When we will get the second next() call, we will return the second left child (from bottom). Now, this node might have a right child. So, before returning this node, we will need to check if it has a right child and push that into stack. From this point, we might have another chain of left children which we should take care of by pushing to the stack until no-one is left (same process that we did in the construction function).

This way, by using stack, we will be able to make the iterator.

###### C++ Code
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class BSTIterator {
public:
stack<TreeNode*> st;
BSTIterator(TreeNode* root) {
while(root != NULL){
st.push(root);
root = root->left; //we will reach until the end by traversing left, and push elements on stack. So, the top most element is the leftmoset element. When someone will call next(), it will return the top most element from stack, which is the leftmost, just like inorder traversal
}
}

int next() {
//Our iterator will return the top most stack element, which is the left most one
TreeNode* cur = st.top();
st.pop();
//we will return cur, but befor that, we need to check if it has any right child or not.
if(cur->right != NULL){
TreeNode* temp = cur->right;
while(temp != NULL){
st.push(temp);
temp = temp->left;
}
}
return cur->val;
}

bool hasNext() {
//if we have any element in stack, we have a next element for the iterator
return st.size() > 0;
}
};

/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator* obj = new BSTIterator(root);
* int param_1 = obj->next();
* bool param_2 = obj->hasNext();
*/```
###### Complexity

Average time complexity is O(1) and space complexity is O(h) where h is the height of tree.

## 7 thoughts on “Binary Search Tree Iterator”

1. Whether you believe in God or not, this is a must-read message!!!

Throughout time, we can see how we have been slowly conditioned to come to this point where we are on the verge of a cashless society. Did you know that the Bible foretold of this event almost 2,000 years ago?

“He (the false prophet who decieves many by his miracles) causes all, both small and great, rich and poor, free and slave, to receive a mark on their right hand or on their foreheads, and that no one may buy or sell except one who has the mark or the name of the beast, or the number of his name.

Here is wisdom. Let him who has understanding calculate the number of the beast, for it is the number of a man: His number is 666.”

Referring to the last generation, this could only be speaking of a cashless society. Why? Revelation 13:17 tells us that we cannot buy or sell unless we receive the mark of the beast. If physical money was still in use, we could buy or sell with one another without receiving the mark. This would contradict scripture that states we need the mark to buy or sell!

These verses could not be referring to something purely spiritual as scripture references two physical locations (our right hand or forehead) stating the mark will be on one “OR” the other. If this mark was purely spiritual, it would indicate only in one place.

This is where it really starts to come together. It is shocking how accurate the Bible is concerning the implatnable RFID microchip. These are notes from a man named Carl Sanders who worked with a team of engineers to help develop this RFID chip

“Carl Sanders sat in seventeen New World Order meetings with heads-of-state officials such as Henry Kissinger and Bob Gates of the C.I.A. to discuss plans on how to bring about this one-world system. The government commissioned Carl Sanders to design a microchip for identifying and controlling the peoples of the world—a microchip that could be inserted under the skin with a hypodermic needle (a quick, convenient method that would be gradually accepted by society).

Carl Sanders, with a team of engineers behind him, with U.S. grant monies supplied by tax dollars, took on this project and designed a microchip that is powered by a lithium battery, rechargeable through the temperature changes in our skin. Without the knowledge of the Bible (Brother Sanders was not a Christian at the time), these engineers spent one-and-a-half-million dollars doing research on the best and most convenient place to have the microchip inserted.

Guess what? These researchers found that the forehead and the back of the hand (the two places the Bible says the mark will go) are not just the most convenient places, but are also the only viable places for rapid, consistent temperature changes in the skin to recharge the lithium battery. The microchip is approximately seven millimeters in length, .75 millimeters in diameter, about the size of a grain of rice. It is capable of storing pages upon pages of information about you. All your general history, work history, crime record, health history, and financial data can be stored on this chip.

Brother Sanders believes that this microchip, which he regretfully helped design, is the “mark” spoken about in Revelation 13:16–18. The original Greek word for “mark” is “charagma,” which means a “scratch or etching.” It is also interesting to note that the number 666 is actually a word in the original Greek. The word is “chi xi stigma,” with the last part, “stigma,” also meaning “to stick or prick.” Carl believes this is referring to a hypodermic needle when they poke into the skin to inject the microchip.”

Mr. Sanders asked a doctor what would happen if the lithium contained within the RFID microchip leaked into the body. The doctor replied by saying a terrible sore would appear in that location. This is what the book of Revelation says:

“And the first (angel) went, and poured out his vial on the earth; and there fell a noisome and grievous sore on the men which had the mark of the beast, and on them which worshipped his image” (Revelation 16:2).

You can read more about it here–and to also understand the mystery behind the number 666: https://2ruth.org/rfid-mark-of-the-beast-666-revealed/

The third angel’s warning in Revelation 14:9-11 states,

“Then a third angel followed them, saying with a loud voice, ‘If anyone worships the beast and his image, and receives his mark on his forehead or on his hand, he himself shall also drink of the wine of the wrath of God, which is poured out full strength into the cup of His indignation. He shall be tormented with fire and brimstone in the presence of the holy angels and in the presence of the Lamb. And the smoke of their torment ascends forever and ever; and they have no rest day or night, who worship the beast and his image, and whoever receives the mark of his name.'”

Who is Barack Obama, and why is he still in the public scene?

So what’s in the name? The meaning of someone’s name can say a lot about a person. God throughout history has given names to people that have a specific meaning tied to their lives. How about the name Barack Obama? Let us take a look at what may be hiding beneath the surface.

Jesus says in Luke 10:18, “…I saw Satan fall like lightning from heaven.”

The Hebrew Strongs word (H1299) for “lightning”: “bârâq” (baw-rawk)

In Isaiah chapter 14, verse 14, we read about Lucifer (Satan) saying in his heart:

“I will ascend above the heights of the clouds, I will be like the Most High.”

In the verses in Isaiah that refer directly to Lucifer, several times it mentions him falling from the heights or the heavens. The Hebrew word for the heights or heavens used here is Hebrew Strongs 1116: “bamah”–Pronounced (bam-maw’)

In Hebrew, the letter “Waw” or “Vav” is often transliterated as a “U” or “O,” and it is primarily used as a conjunction to join concepts together. So to join in Hebrew poetry the concept of lightning (Baraq) and a high place like heaven or the heights of heaven (Bam-Maw), the letter “U” or “O” would be used. So, Baraq “O” Bam-Maw or Baraq “U” Bam-Maw in Hebrew poetry similar to the style written in Isaiah, would translate literally to “Lightning from the heights.” The word “Satan” in Hebrew is a direct translation, therefore “Satan.”

So when Jesus told His disciples in Luke 10:18 that He beheld Satan fall like lightning from heaven, if this were to be spoken by a Jewish Rabbi today influenced by the poetry in the book of Isaiah, he would say these words in Hebrew–the words of Jesus in Luke 10:18 as, And I saw Satan as Baraq O Bam-Maw.

The names of both of Obama’s daughters are Malia and Natasha. If we were to write those names backward (the devil does things in reverse) we would get “ailam ahsatan”. Now if we remove the letters that spell “Alah” (Allah being the false god of Islam), we get “I am Satan”. Coincidence? I don’t think so.

Obama’s campaign logo when he ran in 2008 was a sun over the horizon in the west, with the landscape as the flag of the United States. In Islam, they have their own messiah that they are waiting for called the 12th Imam, or the Mahdi (the Antichrist of the Bible), and one prophecy concerning this man’s appearance is the sun rising in the west.

“Then I saw another angel flying in the midst of heaven, having the everlasting gospel to preach to those who dwell on the earth—to every nation, tribe, tongue, and people— saying with a loud voice, ‘Fear God and give glory to Him, for the hour of His judgment has come; and worship Him who made heaven and earth, the sea and springs of water.'” (Revelation 14:6-7)

Why have the word’s of Jesus in His Gospel accounts regarding His death, burial, and resurrection, been translated into over 3,000 languages, and nothing comes close? The same God who formed the heavens and earth that draws all people to Him through His creation, likewise has sent His Word to the ends of the earth so that we may come to personally know Him to be saved in spirit and in truth through His Son Jesus Christ.

Jesus stands alone among the other religions that say to rightly weigh the scales of good and evil and to make sure you have done more good than bad in this life. Is this how we conduct ourselves justly in a court of law? Bearing the image of God, is this how we project this image into reality?

Our good works cannot save us. If we step before a judge, being guilty of a crime, the judge will not judge us by the good that we have done, but rather by the crimes we have committed. If we as fallen humanity, created in God’s image, pose this type of justice, how much more a perfect, righteous, and Holy God?

God has brought down His moral laws through the 10 commandments given to Moses at Mt. Siani. These laws were not given so we may be justified, but rather that we may see the need for a savior. They are the mirror of God’s character of what He has put in each and every one of us, with our conscious bearing witness that we know that it is wrong to steal, lie, dishonor our parents, murder, and so forth.

We can try and follow the moral laws of the 10 commandments, but we will never catch up to them to be justified before a Holy God. That same word of the law given to Moses became flesh about 2,000 years ago in the body of Jesus Christ. He came to be our justification by fulfilling the law, living a sinless perfect life that only God could fulfill.

The gap between us and the law can never be reconciled by our own merit, but the arm of Jesus is stretched out by the grace and mercy of God. And if we are to grab on, through faith in Him, He will pull us up being the one to justify us. As in the court of law, if someone steps in and pays our fine, even though we are guilty, the judge can do what is legal and just and let us go free. That is what Jesus did almost 2,000 years ago on the cross. It was a legal transaction being fulfilled in the spiritual realm by the shedding of His blood.

For God takes no pleasure in the death of the wicked (Ezekiel 18:23). This is why in Isaiah chapter 53, where it speaks of the coming Messiah and His soul being a sacrifice for our sins, why it says it pleased God to crush His only begotten Son.

This is because the wrath that we deserve was justified by being poured out upon His Son. If that wrath was poured out on us, we would all perish to hell forever. God created a way of escape by pouring it out on His Son whose soul could not be left in Hades but was raised and seated at the right hand of God in power.

So now when we put on the Lord Jesus Christ (Romans 13:14), God no longer sees the person who deserves His wrath, but rather the glorious image of His perfect Son dwelling in us, justifying us as if we received the wrath we deserve, making a way of escape from the curse of death–now being conformed into the image of the heavenly man in a new nature, and no longer in the image of the fallen man Adam.

Now what we must do is repent and put our trust and faith in the savior, confessing and forsaking our sins, and to receive His Holy Spirit that we may be born again (for Jesus says we must be born again to enter the Kingdom of God–John chapter 3). This is not just head knowledge of believing in Jesus, but rather receiving His words, taking them to heart, so that we may truly be transformed into the image of God. Where we no longer live to practice sin, but rather turn from our sins and practice righteousness through faith in Him in obedience to His Word by reading the Bible.

Our works cannot save us, but they can condemn us; it is not that we earn our way into everlasting life, but that we obey our Lord Jesus Christ:

“And having been perfected, He became the author of eternal salvation to all who obey Him.” (Hebrews 5:9)

“Now I saw a new heaven and a new earth, for the first heaven and the first earth had passed away. Also there was no more sea. Then I, John, saw the holy city, New Jerusalem, coming down out of heaven from God, prepared as a bride adorned for her husband. And I heard a loud voice from heaven saying, ‘Behold, the tabernacle of God is with men, and He will dwell with them, and they shall be His people. God Himself will be with them and be their God. And God will wipe away every tear from their eyes; there shall be no more death, nor sorrow, nor crying. There shall be no more pain, for the former things have passed away.’

Then He who sat on the throne said, ‘Behold, I make all things new.’ And He said to me, ‘Write, for these words are true and faithful.’

And He said to me, ‘It is done! I am the Alpha and the Omega, the Beginning and the End. I will give of the fountain of the water of life freely to him who thirsts. He who overcomes shall inherit all things, and I will be his God and he shall be My son. But the cowardly, unbelieving, abominable, murderers, sexually immoral, sorcerers, idolaters, and all liars shall have their part in the lake which burns with fire and brimstone, which is the second death.'” (Revelation 21:1-8).

2. Dear foolishhungry.com admin, Great post!

3. To the foolishhungry.com webmaster, Your posts are always well organized and easy to understand.