FilesExpand file tree

 master

/

binarySearchTreeIterator.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

65 lines (41 loc) · 1.44 KB

 master

/

binarySearchTreeIterator.java

Copy path

Top

File metadata and controls

• Code
• Blame

65 lines (41 loc) · 1.44 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

// 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.

// Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

/**

* Definition for binary tree

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class BSTIterator {

Stack<TreeNode> stack;

public BSTIterator(TreeNode root) {

stack = new Stack<TreeNode>();

while(root != null) {

stack.push(root);

root = root.left;

}

}

/** @return whether we have a next smallest number */

public boolean hasNext() {

return stack.isEmpty() ? false : true;

}

/** @return the next smallest number */

public int next() {

TreeNode nextSmallest = stack.pop();

TreeNode addToStack = nextSmallest.right;

while(addToStack != null) {

stack.add(addToStack);

addToStack = addToStack.left;

}

return nextSmallest.val;

}

}

/**

* Your BSTIterator will be called like this:

* BSTIterator i = new BSTIterator(root);

* while (i.hasNext()) v[f()] = i.next();

*/