## Tree - 173. Binary Search Tree Iterator

Published on with 0 views and 0 comments

173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling `next()` will return the next smallest number in the BST.

Example:

``````BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false
``````

go：

``````/**

* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

type BSTIterator struct {
Stack *list.List
}

func Constructor(root *TreeNode) BSTIterator {
bsti := BSTIterator{Stack:list.New()}
bsti.push(root)
return bsti
}

/** @return the next smallest number */
func (this *BSTIterator) Next() int {
e := this.Stack.Back()
cur := e.Value.(*TreeNode)
this.Stack.Remove(e)

this.push(cur.Right)
return cur.Val
}

/** @return whether we have a next smallest number */
func (this *BSTIterator) HasNext() bool {
return this.Stack.Len() != 0
}

func (this *BSTIterator) push(node *TreeNode) {
for node != nil {
this.Stack.PushBack(node)
node = node.Left
}
}

/**
* Your BSTIterator object will be instantiated and called as such:
* obj := Constructor(root);
* param_1 := obj.Next();
* param_2 := obj.HasNext();
*/
``````